Algorithms/Search: Difference between revisions
From charlesreid1
(Created page with "=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...") |
|||
| Line 14: | Line 14: | ||
<math> | <math> | ||
(mid - 1) - low + 1 = | (mid - 1) - low + 1 = floor( \dfrac{low+high}{2} ) - low \leq \dfrac{high - low + 1}{2} | ||
</math> | </math> | ||
Revision as of 00:37, 12 July 2017
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} $