I know binary search but most of the time I gets confused how to find mid index and what to return low or high.
There are two while loop conditions:
1. while(low<high)
2. while(low<=high)
There are two ways to find mid element:
1. mid = (low+high)/2
2. mid = (low+high+1)/2
And then depending on the required condition we do low = mid+1 and right = mid or low = mid and right = mid-1 or something else. I know it's something keeping low always as our answer and returning that after while loop breaks and if high is always possible answer we return high. But I don't know clearly what to do when. Is there any logical way to do this stuff, I have try some combinations before getting right pair of conditions.
Thanks in advance.
There are two easy binary search approaches and one hard.
Easy 1.
Always maintain closed interval and the best answer outside this interval. Your template will be:
Instead of dots:
left = mid + 1
andright = mid - 1
depending on your condition. It's always easy to see in which branch left or right border should be reassigned.ans = mid
. Again, it's always easy to see in which one. Ifmid
would be the better answer thenans
, assign.Easy 2.
It's called binary lifting. The template looks like this:
I don't think this even requires any comments, it's just obvious. Absolutely no +/-1 errors.
Hard.
Let's wait when some red appears and writes it's the only true way. Who cares when you can literally make a mistake in EVERY expression.
I often use the second loop condition,
while (low <= high)
, and the first way to find index of the middle element,mid = (low+high)/2
. To update one of the limits, eitherlow = mid+1
orhigh = mid-1
, it is sufficient to keep in mind that the function $$$f$$$ computed atmid
should be non-decreasing function, i.e. $$$f(mid-\delta) \leq f(mid) \leq f(mid+ \delta)$$$ for any positive value $$$\delta$$$.