Binary search: Difference between revisions
| (3 intermediate revisions by the same user not shown) | |||
| Line 7: | Line 7: | ||
== Abstract view == | == Abstract view == | ||
The subroutine does nothing but calling another, recursive subroutine with the same output and the following input: array <math>A</math>, element <math>s</math>, comparison <math>cmp</math> | The subroutine does nothing but calling another, recursive subroutine with the same output and the following input: array <math>A</math>, element <math>s</math>, comparison <math>cmp</math> and, in addition, two indices of <math>A</math>, <math>\ell</math> and <math>r</math>, such that <math>\ell<r</math>. In the original call to this recursive subroutine, <math>\ell</math> is the first and <math>r</math> the last index of <math>A</math>. | ||
'''Invariant:''' For every recursive call: | '''Invariant:''' For every recursive call: | ||
| Line 25: | Line 25: | ||
# If <math>A[m]=s</math> terminate and return <math>m</math>. | # If <math>A[m]=s</math> terminate and return <math>m</math>. | ||
# Otherwise, if <math>s</math> precedes <math>A[m]</math> with respect to <math>cmp</math>, apply a recursive call with <math>A</math>, <math>s</math>, <math>cmp</math>, <math>\ell</math> and<math>m-1</math>. | # Otherwise, if <math>s</math> precedes <math>A[m]</math> with respect to <math>cmp</math>, apply a recursive call with <math>A</math>, <math>s</math>, <math>cmp</math>, <math>\ell</math> and<math>m-1</math>. | ||
# Otherwise, apply a recursive call with <math>A</math>, <math>s</math>, <math>cmp</math>, <math>m+1</math> and<math>r</math>. | # Otherwise, apply a recursive call with <math>A</math>, <math>s</math>, <math>cmp</math>, <math>m+1</math> and <math>r</math>. | ||
'''Correctness:''' obvious. | |||
== Complexity == | == Complexity == | ||
'''Statement:''' | '''Statement:''' The asymptotic complexity is in <math>\mathcal{O}(\log n)</math>. | ||
''' | '''Proof:''' follows immediately from the variant. | ||
Latest revision as of 06:29, 27 April 2016
Binary search
Algorithmic problem: Finding an element in a sorted array
Type of algorithm: recursion
Abstract view
The subroutine does nothing but calling another, recursive subroutine with the same output and the following input: array [math]\displaystyle{ A }[/math], element [math]\displaystyle{ s }[/math], comparison [math]\displaystyle{ cmp }[/math] and, in addition, two indices of [math]\displaystyle{ A }[/math], [math]\displaystyle{ \ell }[/math] and [math]\displaystyle{ r }[/math], such that [math]\displaystyle{ \ell\lt r }[/math]. In the original call to this recursive subroutine, [math]\displaystyle{ \ell }[/math] is the first and [math]\displaystyle{ r }[/math] the last index of [math]\displaystyle{ A }[/math].
Invariant: For every recursive call: If [math]\displaystyle{ s }[/math] is present at least once in [math]\displaystyle{ A }[/math], then all indices of [math]\displaystyle{ A }[/math] where [math]\displaystyle{ s }[/math] is present are in the interval [math]\displaystyle{ [\ell,\ldots,r] }[/math].
Variant: The value [math]\displaystyle{ r-\ell }[/math] is roughly halved in every descent in the recursion tree.
Break condition: Either an occurrence of [math]\displaystyle{ s }[/math] is found or it is [math]\displaystyle{ \ell\gt r }[/math]
Induction basis
The invariant is trivially fulfilled because [math]\displaystyle{ [\ell,\ldots,r] }[/math] is the entire index range of [math]\displaystyle{ A }[/math].
Induction step
- Set [math]\displaystyle{ m:=(\ell+r)/2 }[/math].
- If [math]\displaystyle{ A[m]=s }[/math] terminate and return [math]\displaystyle{ m }[/math].
- Otherwise, if [math]\displaystyle{ s }[/math] precedes [math]\displaystyle{ A[m] }[/math] with respect to [math]\displaystyle{ cmp }[/math], apply a recursive call with [math]\displaystyle{ A }[/math], [math]\displaystyle{ s }[/math], [math]\displaystyle{ cmp }[/math], [math]\displaystyle{ \ell }[/math] and[math]\displaystyle{ m-1 }[/math].
- Otherwise, apply a recursive call with [math]\displaystyle{ A }[/math], [math]\displaystyle{ s }[/math], [math]\displaystyle{ cmp }[/math], [math]\displaystyle{ m+1 }[/math] and [math]\displaystyle{ r }[/math].
Correctness: obvious.
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(\log n) }[/math].
Proof: follows immediately from the variant.