Whenever I revisit binary search problems, I keep having to work out the edge cases whenever coming up with the algorithm. So I thought I’d make a note of the pseudo code template I always end up with:
l=0, r=a.size()-1
while (l <= r) {
m = l+(r-l)/2
if (a[m] == target) return m
if (a[m] < target) l = m+1
else r = m-1
}
return -1 //not found
Note that we use m = l+(r-l)/2, rather than m=(l+r)/2, to ensure that we don’t get integer overflow.
We don’t have to have an array for a binary search. If we want to find sqrt(x), then we can set left=0 and right=x. We then test if mid is our sqrt number by squaring it: m*m.
We can also use floating point numbers. But then we need a different end case based on precision. So, to find sqrt(x) for a floating point number we would do something like:
l=0, r=x
while (r-l > 0.001) {
m = l+(r-l)/2
if (m*m == x) return m
else if (m*m > x) r = m
else l = m
}
return m
There’s a chance we will guess m exactly, in which case we return m in the loop. But most likely we will get to within our precision limit and exit the loop and then we will return m.
We can use comparison constraint rather than an exact target match by adapting our binary search algorithm. So, let’s say we want to find the smallest value bigger than or equal to x, i.e. find first value >= x. We will use an answer variable (ans) to keep track of the latest mid value we’ve found that satisfies our criteria. If mid doesn’t satisfy our criteria then we look in the half that will get us closer, so in this case if our target is 6 and we find 2 then we need to search the right half. We can let the while loop run its course rather than terminating it early.
l=0, r=a.size()-1, ans=-1
while (l <= r) {
m = l+(r-l)/2
if (a[m] >= x) {
ans = a[m]
r = m-1
}
else
l = m+1
}
return ans
This is a nice video lecture about binary search:
https://www.youtube.com/watch?v=GU7DpgHINWQ