Menu
The value of low cannot be greater than high; this means that the key is not in the vector. So, the algorithm repeats until either the key is found or until low > high, which means that the key is not there. The following function implements this binary search algorithm.
If the search value is same as mid index value then element is found and you stop processing. This divide and compare process continues until you find the search element or left and right index (initially 0 and length-1) overlaps. Thats why the condition left <= right .
To ensure binary search termination, make sure the mid (and so left or right) change on every iteration. If we can reason or determine that mid value will always change, we can be 100% confidence that the binary search will not be struck in the infinite loop.
Mathematically Maximum iteration possible (Assuming case of only integer type) is = ceil( log2 ( initial_r - initial_l ) ) base of log is 2 because every time we are diving our range in half by taking a mid and switching to one of the half.
Suppose you are searching a 4000000000-element array using 32-bit unsigned int as indexes.
The first step made it appear as though the searched element, if present, would be in the top half. lo's value is 2000000000 and hi's is 4000000000.
hi + lo overflows and produces a value smaller than the intended 6000000000. It actually produces 6000000000-232. As a result, (hi + lo) / 2 is a small value. It is not even between lo and hi!
From then on the search will be wrong (it will probably conclude that the element is absent even if it was there).
By contrast, even with the extreme values in this example, lo + (hi - lo) / 2 always computes an index halfway between hi and lo, as intended by the algorithm.
Mathematically speaking, they are equivalent.
In computer terms, mid=(hi+lo)/2 has fewer operations, but mid=lo+(hi-lo)/2 is preferred to avoid overflow.
Say the item you are searching are near the end of the array, then hi+lo is nearly 2*size. Since size can be almost as large as your maximum index, 2*size and thus hi+lo can overflow.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With