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} $