Algorithms/Search: Difference between revisions
From charlesreid1
| Line 15: | Line 15: | ||
<math> | <math> | ||
(mid - 1) - low + 1 = floor( \dfrac{low+high}{2} ) - low \leq \dfrac{high - low + 1}{2} | (mid - 1) - low + 1 = floor( \dfrac{low+high}{2} ) - low \leq \dfrac{high - low + 1}{2} | ||
</math> | |||
or, | |||
<math> | |||
high - (mid+1) + 1 = high - floor( \dfrac{low + high}{2} \leq \dfrac{high - low + 1}{2} | |||
</math> | </math> | ||
Revision as of 00:38, 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} $
or,
$ high - (mid+1) + 1 = high - floor( \dfrac{low + high}{2} \leq \dfrac{high - low + 1}{2} $