<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Udit Mehta on Medium]]></title>
        <description><![CDATA[Stories by Udit Mehta on Medium]]></description>
        <link>https://medium.com/@uditmehta100?source=rss-a71e8cde8877------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*XsBCq9OZmXkrn3dR</url>
            <title>Stories by Udit Mehta on Medium</title>
            <link>https://medium.com/@uditmehta100?source=rss-a71e8cde8877------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 07:11:28 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@uditmehta100/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Binary Search on Answer]]></title>
            <link>https://medium.com/@uditmehta100/binary-search-on-answer-cfde46e83b43?source=rss-a71e8cde8877------2</link>
            <guid isPermaLink="false">https://medium.com/p/cfde46e83b43</guid>
            <category><![CDATA[binary-search]]></category>
            <dc:creator><![CDATA[Udit Mehta]]></dc:creator>
            <pubDate>Sun, 09 Feb 2025 11:03:39 GMT</pubDate>
            <atom:updated>2025-02-09T11:03:39.989Z</atom:updated>
            <content:encoded><![CDATA[<p>Binary search is useful in many situations. For example, interactive problems or minimizing the maximum problems. Binary search is a good choice when dealing with many situations, and for many binary search problems, monotonousness may be hard to find out and participants may not be able to focus on binary search.</p><p>You may think that binary search is simple, but after this blog, you may think more about how binary search is working on competitive programming.</p><h3>Part A — What is binary search?</h3><p>Consider the following problem: you are going to guess a number between 0 and 100, and I’ll tell you that the number you give is smaller than the number I thought about or not. How to minimize the number of your guessing?</p><p>Well, you may guess 50 first, if 50 is too large, guess 25, otherwise 75, and so on. For each guess, you cut off half the possible numbers, since 𝑥 is small, the numbers smaller than 𝑥 are also small. If 𝑥 is large, the numbers larger than 𝑥 are also big.</p><p>The number of your guessing will be <strong>at most</strong> log100 times. If changed 100 to 𝑛, the complexity of the guessing will be <strong>at most </strong>O(log⁡n).</p><p>Why are you using binary search when seeing the problem? Let’s consider the following monotonous function 𝑓(𝑥):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Frx26cu5ZGN0NU9iNebuMQ.png" /></figure><p>And you are querying the middle place, if too small:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*VpCe-O07_D4CF7qDYoeWRw.png" /></figure><p>Otherwise, it’s just opposite.</p><p>This is the motivation for doing binary search. Only if <strong>monotonousness</strong> is known, binary search can be performed. Otherwise, binary search cannot be performed since the half part cannot be considered useless.</p><h3>Part B — Implementation</h3><p>Here we give out a standard code below:</p><pre>bool check(int x) {<br>	//something<br>}<br>signed main() {<br>  //...<br>  l = 1, r = maxn;<br>  while(l &lt;= r) {<br>		int mid = (l + r) / 2;<br>		if(chk(mid)) l = mid + 1;<br>		else r = mid - 1;<br>	}<br>	cout &lt;&lt; l - 1 &lt;&lt; endl;<br>	return 0;<br>}</pre><p>The final l−1 is the largest value x with check(x) = 1.</p><p>To help understanding, let’s write out the guessing number code.</p><pre>#include&lt;bits/stdc++.h&gt;<br>#define int long long<br>using namespace std;<br>bool chk(int x) {<br>	cout &lt;&lt; &quot;&gt;= &quot; &lt;&lt; x &lt;&lt; endl;<br>  string str; cin &gt;&gt; str;<br>  if(str == &quot;Yes&quot;) return 1;<br>  return 0;<br>}<br>const int maxn = 100;<br>signed main() {<br>  int l = 1, r = maxn;<br>  while(l &lt;= r) {<br>		int mid = (l + r) / 2;<br>		if(chk(mid)) l = mid + 1;<br>		else r = mid - 1;<br>	}<br>	cout &lt;&lt; &quot;! &quot; &lt;&lt; l - 1 &lt;&lt; endl;<br>	return 0;<br>}</pre><p>For example, we are guessing the number 88, this is the process:</p><pre>&gt;= 50<br>Yes<br>&gt;= 75<br>Yes<br>&gt;= 88<br>Yes<br>&gt;= 94<br>No<br>&gt;= 91<br>No<br>&gt;= 89<br>No<br>! 88</pre><h3>Part C — Basic binary search situations</h3><p><strong>Task C1</strong></p><p>You’ve got 𝑛n trees, the i-th tree has the height of ℎ𝑖 meters. You are going to cut them. You are going to determine a value 𝑥, which is the height of the saw. And then:</p><ul><li>For trees with hi≥x, do hi←x, and you will get (ℎ𝑖−𝑥) meters of wood.</li><li>For trees with hi&lt;x, nothing changes.</li></ul><p>You want to get m meters of wood from the trees, to protect the environment, what’s the largest x you can determine?</p><ul><li>1≤𝑛≤10^6.</li><li>1≤ℎ𝑖≤2×10^9</li></ul><p><strong>Solution of Task C1</strong></p><p>It’s obvious that, when the x increases, the length of the wood you get decreases. This means that the monotonousness of the problem is very clear. Due to this, let’s do binary search:</p><pre>#include &lt;bits/stdc++.h&gt;<br>#define int long long<br>#define rep(i, l, r) for(int i = (l); i &lt;= (r); i++)<br>using namespace std;<br>int A[1000005], n, m;<br>bool chk(int x) {<br>	int sum = 0;<br>	rep(i, 1, n) {<br>		if(A[i] &gt; x) sum += (A[i] - x);<br>	} return sum &gt;= m;<br>}<br>signed main() {<br>	int maxn = 0;<br>	cin &gt;&gt; n &gt;&gt; m;<br>	rep(i, 1, n) {<br>		cin &gt;&gt; A[i];<br>		maxn = max(A[i], maxn);<br>	} <br>        int l = 1, r = maxn;<br>	while(l &lt;= r) {<br>		int mid = (l + r) / 2;<br>		if(chk(mid)) l = mid + 1;<br>		else r = mid - 1;<br>	}<br>	cout &lt;&lt; l - 1 &lt;&lt; endl;<br>	return 0;<br>}</pre><p><strong>Task C2</strong></p><p>You’ve got an array 𝑎1,𝑎2,𝑎3,…,𝑎𝑛 and you are going to devide the array into 𝑚m segments. You are going to minimize the maximum number of the sum of the subsegments.</p><p>For example, 𝑎=[4,2,4,5,1],𝑚=3 the answer is 6 since [4,2][4][5,1] is possible, and max(6,4,6)=6 which is the best.</p><ul><li>1≤𝑚≤𝑛≤10^5.</li><li>0≤𝑎𝑖≤10^8.</li></ul><p><strong>Solution of Task C2</strong></p><p>We can find out that, the larger the maxinum is, the fewer segments will be needed. This leads to the monotonousness. And then we can do binary search on the maxinum, and if the mininum needed segments is no more than 𝑚m, it seems that the mininum can be reached, otherwise it cannot be reached.</p><p>So this is the check function:</p><pre>bool check(int x) {<br>  int s = 0, ret = 0;<br>  for(int i = 1; i &lt;= n; i++) {<br>    if(s + a[i] &gt; x) ret++, s = 0;<br>    s += a[i];<br>  }<br>  return ret &gt;= m;<br>}</pre><p>Complete code example:</p><pre>#include&lt;bits/stdc++.h&gt;<br>#define int long long<br>using namespace std;<br>int a[200005], n, m;<br>bool check(int x) { /* See above */ }<br>signed main() {<br>  cin &gt;&gt; n &gt;&gt; m;<br>  int sum = 0, maxn = 0;<br>  for(int i = 1; i &lt;= n; i++) <br>    cin &gt;&gt; a[i], sum += a[i], maxn = max(maxn, a[i]);<br>  int l = maxn, r = sum;<br>  while(l &lt;= r) {<br>		int mid = (l + r) / 2;<br>		if(chk(mid)) l = mid + 1;<br>		else r = mid - 1;<br>	}<br>  cout &lt;&lt; l &lt;&lt; endl;<br>}</pre><h3>Ending</h3><p>This blog talked about basic binary search algorithm . Solve More Problems by your own so you will get clear understading of that topic</p><p><a href="https://codeforces.com/problemset/problem/1873/E">https://codeforces.com/problemset/problem/1873/E</a><br><a href="https://codeforces.com/problemset/problem/1345/B">https://codeforces.com/problemset/problem/1345/B</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cfde46e83b43" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>