When performing a binary search on answer, I've seen different forms of the following:
loop condition : (low+1<hi), (low<hi), (low<=hi) updating indices: (hi=mid+1), (hi=mid), (low=mid), (low=mid-1)
What is the difference between these and do they actually matter?
Each of the loop conditions simply state when the loop will end. If you want to find exactly one element lo < hi is usually the easiest method. For two elements, or lo + 1 < hi could be used. lo <= hi is usually paired with an early return statement in the while loop.
Before updating the indices, a mid is chosen usually either (lo + hi) / 2 or (lo + hi + 1) / 2 (ignoring integer overflow). The difference between these is that the first has a bias towards lo if there are an even number of elements between lo and hi, whereas the second has a bias towards hi.
The updating indices have + 1 attached to them to ensure that there is no infinite loop. In general, you want to make sure lo and hi are modified by at least 1 for every iteration of the loop.
For reference, here is my preferred way of doing binary search:
int binary_search(std::vector<int> nums, int target) {
if (nums.empty())
return -1;
int l = 0;
int h = nums.size() - 1;
while (l < h) {
// If the language doesn't have big ints, make sure there is no overflow.
// This has a left bias if there are an even number of elements left.
int m = l + (h - l) / 2;
if (nums[m] < target) {
// The `+ 1` here is important. Without this, if there are two elements
// and nums[0] < target, we'll get an infinite loop.
l = m + 1;
} else {
// Since `m < h`, we "make progress" in this case.
h = m;
}
}
return nums[l] == target ? l : -1;
}
I like this method, because it is clear that there is no infinite loop, and the exit condition does not rely on early return statements.
