Search code examples
c++algorithmbinary-search

Why we write lo+(hi-lo)/2 in binary search?

I was reading about binary search...I know that the traditional way of finding mid value is like

mid=(hi+lo)/2

But i also see that to avoid overflow mid value is calculated like that

mid=lo+(hi-lo)/2

But why?? I couldn't find the actual reason..Can anyone give me the reason with example?? It is different from other question because other questions didn't have the answer that i wanted with example...

Solution

  • 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.