binary search (l+r)/2 or (l+r+1)/2 i saw this on a topcoder article that one or the other will no give while loop but on some test cases both might not as can be seen in submission 76258234 is where i changed (r+l)/2 to r+l+1/2 from this submission 76258059 and my solution passed so how to decide which one will never give a while loop right now i just do it randomly one and if that doesnt pass i do other
Auto comment: topic has been updated by 2020 (previous revision, new revision, compare).
If your binary search is like this:
if(something) hi = mid;
else lo = mid + 1;
then it should be (lo + hi) / 2, and otherwise (lo = mid or hi = mid – 1) it should be (lo + hi + 1) / 2.
from where you learned this trick, I was also confused between them
Before I discovered that, I always used (lo + hi) / 2 and added some ifs to prevent TLE. Later, I found out I can just use (lo + hi + 1) instead.
be careful on negative borders. if your condition is
while(lo < hi)
it can be loopedjust
mid = (lo + hi) >> 1
I check for case r = l + 1 to decide
Not sure why this is so downvoted. Understanding invariants and all is of course good, but I often just consider the case L = 0, R = 1 to choose between (L+R)/2 or (L+R+1)/2 – it's faster :)
Another ugly method I sometimes (shamefully) use – just write (L+R)/2, if the program doesn't terminate, change it to (L+R+1)/2. :D
Don't use this, no guarantees, etc.
Suppose you have a predicate $$$P(n)$$$ which goes from being false to being true as $$$n$$$ increases, and you want to find the least $$$n$$$ for which it is true. There are two things to remember so you never get a binary search wrong:
1) Remember the invariant you are maintaining! At the end, you'll have $$$l = r$$$, $$$P(l-1)$$$ false and $$$P(l)$$$ true, so a good invariant is to say that $$$P(l-1)$$$ should always be false and $$$P(r)$$$ should always be true. With this, you can initialize the variables appropriately. Now let's look at the iteration steps:
2) Both updates must decrease the length of the interval $$$[l, r]$$$, and we must round up or down to ensure that. Let's check the above code is correct: Since $$$l < r$$$, we have that (as real numbers) $$$l < \frac{l+r}{2} < r$$$, and therefore
l <= (l+r)/2 < r
after rounding down. Therefore,r = mid
decreases $$$r$$$ andl = mid+1
increases $$$l$$$.Let's do the same for a predicate $$$P(n)$$$ that goes from being true to being false as $$$n$$$ increases. Suppose we want to find the largest $$$n$$$ for which $$$P(n)$$$ is true. Then at the end, we will have $$$l = r$$$, $$$P(l)$$$ true and $$$P(l+1)$$$ false. Therefore, the invariant we will maintain is that $$$P(l)$$$ should always be true and $$$P(r+1)$$$ should always be false. How does the code look like in this case?
Now, it is still true that (as real numbers) $$$l < \frac{l+r}{2} < r$$$. But if we want
l = mid
to increase $$$l$$$, then we cannot round the division down. Rounding it up (by doing(l+r+1)/2
) is fine, because thenl < (l+r+1)/2 <= r
, and thereforer = mid - 1
decreases $$$r$$$ andl = mid
increases $$$l$$$.thanks man that was really good
if I use
then
l = mid + 1
andr = mid - 1
right ?I absolutely don't understand why you don't use binsearch, that ends with $$$l + 1 = r$$$. In this case invariant will be easier: $$$P(l)$$$ always be false and $$$P(r)$$$ always be true.
So, the second thing is not necessary — if $$$r - l > 1$$$, then $$$l < \left \lfloor \frac{l + r}{2} \right \rfloor \leq \left \lceil \frac{l + r}{2} \right \rceil < r$$$ and length of the interval will decreases anyway. Thus you can use whatever you want — both formulas will work.
Code looks like this:
But you have to think about $$$l$$$ and $$$r$$$ at start. Often it is enough to set $$$l = -1$$$ and $$$r = n$$$ if you use binserch to find in array with indexes $$$[0 \ldots n - 1]$$$.
Obviously,
(l + r) / 2
equals $$$\left \lfloor \frac{l + r}{2} \right \rfloor$$$ and(l + r + 1) / 2
equals $$$\left \lceil \frac{l + r}{2} \right \rceil$$$.Normally, if the smaller l is, the more possible check(mid) will be true, use (l+r+1)/2. Otherwise, use (l+r)/2.
https://codeforces.net/blog/entry/67509
Btw, I see so many website use mid = low + (high — low) / 2. So how it differ from mid = (low + high) / 2 ?
To prevent overflow. (low + high) is computed before dividing by 2 so may cause overflow.
I got it, thank a lot!