Binary Search - Why?
I am studying a binary search algorithm and I have seen many times the algorithm written as follows (this is C ++, but the language is not that important here):
int start = 0;
int end = vec.size() - 1;
do {
int mid = (lo + hi) / 2;
if (target < vec[mid])
start = mid + 1;
else if (target > vec[mid])
end = mid - 1;
else
// found
} while (start <= end);
However, I've also seen implementations like this:
int start = 0;
int end = vec.size() - 1;
do {
int mid = (int)ceil((lo + hi) / 2.0);
if (target < vec[mid])
start = mid + 1;
else if (target > vec[mid])
end = mid - 1;
else
// found
} while (start <= end);
Both seem to work. Is there any correctness or performance reason why I should get ceil
and execute this second order floating point arithmetic instead of the first version?
source to share
When int mid = (lo + hi) / 2
:
You accept an element mid
by taking the left element of the two potential middle elements when the size of the array between [left, right] is odd, ie. for array [4, 5] your mean would be 4. So without any ceil
of floor
, division works like floor
.
When (int)ceil((lo + hi) / 2.0);
:
You define an element mid
by taking the right element from two potential middle elements when the size of the array between [left, right] is odd, i.e. for [4, 5] your average will be 5.
Thus, both the choice of going to work, because you drop / take part based on some acceptable conditions ( target < vec[mid]
and target > vec[mid]
). The split point doesn't matter here.
Another thing is, while working, for example int mid = (lo + hi) / 2
, you may encounter overflow when adding lo
and hi
if the sum exceeds an integer range. It is as safe to write as mid = lo + (hi - lo) / 2
, which will give the same result.
Hope it helps!
Edit
so both only work because I am discarding the middle item from the new search range when I run the search again, right?
Yes. If you haven't dropped the element mid
, it will end up in an infinite loop, i.e. [4, 5], 4 will always be selected as mid
, and for a type call left = mid
it will create an infinite loop.
source to share