Algorithms/Search

Notes

Goodrich chapter 4

Recursion: binary search analysis.

Proposition: The binary search algorithm runs in O(log n) time for a sorted sequence with n elements.

Justification: To prove this claim, a crucial fact is that within each recursive call the number of candidate entries still to be searched is given by the value

high - low + 1

Moreover, the number of remaining candidates is reduced by at least one half with each recursive call. Specifically, from the definition of mid, the number of remaining candidates is either

$ (mid - 1) - low + 1 = floor( \dfrac{low+high}{2} ) - low \leq \dfrac{high - low + 1}{2} $

or,

$ high - (mid+1) + 1 = high - floor( \dfrac{low + high}{2} ) \leq \dfrac{high - low + 1}{2} $

Initially, n candidates; next call, n/2 candidates; next call, n/4 candidates; etc. The maximum number of recursive calls is the smallest integer r such that:

$ \dfrac{n}{2^r} < 1 $

In other words, $ r > \log{(n)} $

Thus, we have

$ r = floor( \log{(n)} ) + 1 $

which implies that binary search runs in O(log N) time.