## You are here

Homebinary search

## Primary tabs

# binary search

# The Problem

Let $\leq$ be a total ordering on the set $S$. Given a sequence of $n$ elements, $L=\left\{x_{1}\leq x_{2}\leq\dots\leq x_{n}\right\}$, 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 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 $key<L[middle]$ then

$Find\leftarrow Find(L,bottom,middle-1,key)$

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 $\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}(\log{n})$. It can also be shown that the average-case runtime complexity of the binary search is approximately $\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).

## Mathematics Subject Classification

68P10*no label found*16S40

*no label found*20G42

*no label found*16W35

*no label found*81R50

*no label found*16W30

*no label found*57T05

*no label found*54-01

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Comments

## Algorithm

Imagine that you are in a building with F floors (starting at floor 1, the lowest floor), and you have a large number of identical eggs, each in its own identical protective container. For each floor in the building, you want to know whether or not an egg dropped from that floor will break. If an egg breaks when dropped from floor i, then all eggs are guaranteed to break when dropped from any floor j â‰¥ i. Likewise, if an egg doesn't break when dropped from floor i, then all eggs are guaranteed to never break when dropped from any floor j â‰¤ i.

Define an algorithm with inputs(F, D, B) and output that determines whether or not an egg will break when dropped from any floor of a building with F floors, with the following restrictions: you may drop a maximum of D eggs (one at a time, from any floors of your choosing), and you may break a maximum of B eggs. You can assume you have at least D eggs in your possession.