# Binary 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 $A$, element $s$, comparison $cmp$ and, in addition, two indices of $A$, $\ell$ and $r$, such that $\ell\lt r$. In the original call to this recursive subroutine, $\ell$ is the first and $r$ the last index of $A$.

Invariant: For every recursive call: If $s$ is present at least once in $A$, then all indices of $A$ where $s$ is present are in the interval $[\ell,\ldots,r]$.

Variant: The value $r-\ell$ is roughly halved in every descent in the recursion tree.

Break condition: Either an occurrence of $s$ is found or it is $\ell\gt r$

## Induction basis

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

## Induction step

1. Set $m:=(\ell+r)/2$.
2. If $A[m]=s$ terminate and return $m$.
3. Otherwise, if $s$ precedes $A[m]$ with respect to $cmp$, apply a recursive call with $A$, $s$, $cmp$, $\ell$ and$m-1$.
4. Otherwise, apply a recursive call with $A$, $s$, $cmp$, $m+1$ and $r$.

Correctness: obvious.

## Complexity

Statement: The asymptotic complexity is in $\mathcal{O}(\log n)$.

Proof: follows immediately from the variant.