# binary search

## The Problem

Let $\le $ be a total ordering^{} on the set $S$. Given a sequence of $n$ elements,
$L=\{{x}_{1}\le {x}_{2}\le \mathrm{\dots}\le {x}_{n}\}$, and a value $y\in S$,
locate the position of any elements in $L$ that are equal to $y$, or determine that
none exist.

## The Algorithm

The *binary search ^{}* technique is a fundamental method for locating an element of
a particular value within a sequence of sorted elements (see Sorting Problem).
The idea is to eliminate half of the search space with each comparison.

First, the
middle element of the sequence is compared to the value we are searching for. If this
element matches the value we are searching for, we are done. If, however, the middle
element is “less than” the value we are chosen for (as specified by the relation^{} (http://planetmath.org/Relation) used
to specify a total order over the set of elements), then we know that, if the value exists
in the sequence, it must exist somewhere *after* the middle element. Therefore we
can eliminate the first half of the sequence from our search and simply repeat the search
in the exact same manner on the remaining half of the sequence. If, however, the value we
are searching for comes before the middle element, then we repeat the search on the first half
of the sequence.

## Pseudocode

Algorithm^{} Binary_Search(L, n, key)

Input: A list $L$ of $n$ elements, and $key$ (the search key)

Output: $Position$ (such that $X[Position]=key$)

begin

$Position\leftarrow Find(L,1,n,key);$

end

function $Find(L,bottom,top,key)$

begin

if $bottom=top$ then

if $L[bottom]=key$ then

$Find\leftarrow bottom$

else

$Find\leftarrow 0$

else

begin

$middle\leftarrow (bottom+top)/2;$

if $$ then

else

$Find\leftarrow Find(L,middle+1,top,key)$

end

end

## Analysis

We can specify the runtime complexity of this binary search algorithm by counting the number of comparisons required to locate some element $y$ in $L$. Since half of the list is eliminated with each comparison, there can be no more than ${\mathrm{log}}_{2}n$ comparisons before either the positions of all the $y$ elements are found or the entire list is eliminated and $y$ is determined to not exist in $L$. Thus the worst-case runtime complexity of the binary search is $\mathcal{O}(\mathrm{log}n)$. It can also be shown that the average-case runtime complexity of the binary search is approximately ${\mathrm{log}}_{2}n-1$ comparisons. This means that any single entry in a phone book containing one million entries can be located with at most 20 comparisons (and on average 19).

Title | binary search |

Canonical name | BinarySearch |

Date of creation | 2013-03-22 11:44:34 |

Last modified on | 2013-03-22 11:44:34 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 18 |

Author | mathcam (2727) |

Entry type | Algorithm |

Classification | msc 68P10 |

Classification | msc 16S40 |

Classification | msc 20G42 |

Classification | msc 16W35 |

Classification | msc 81R50 |

Classification | msc 16W30 |

Classification | msc 57T05 |

Classification | msc 54-01 |

Related topic | TotalOrder |

Related topic | PartialOrder |

Related topic | SortingProblem |

Related topic | InsertionSort |