Binary search

From Algowiki
Jump to: navigation, search

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]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\lt 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: If [math]s[/math] is present at least once in [math]A[/math], then all indices of [math]A[/math] where [math]s[/math] is present are in the interval [math][\ell,\ldots,r][/math].

Variant: The value [math]r-\ell[/math] is roughly halved in every descent in the recursion tree.

Break condition: Either an occurrence of [math]s[/math] is found or it is [math]\ell\gt r[/math]

Induction basis

The invariant is trivially fulfilled because [math][\ell,\ldots,r][/math] is the entire index range of [math]A[/math].

Induction step

  1. Set [math]m:=(\ell+r)/2[/math].
  2. If [math]A[m]=s[/math] terminate and return [math]m[/math].
  3. 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].
  4. 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

Statement: The asymptotic complexity is in [math]\mathcal{O}(\log n)[/math].

Proof: follows immediately from the variant.