Algorithms/Search
From charlesreid1
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} $