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 thatnone exist.

The Algorithm

The binary search technique is a fundamental method for locating an element ofa 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, themiddle element of the sequence is compared to the value we are searching for. If thiselement matches the value we are searching for, we are done. If, however, the middleelement is “less than” the value we are chosen for (as specified by the relation (http://planetmath.org/Relation) usedto specify a total order over the set of elements), then we know that, if the value existsin the sequence, it must exist somewhere after the middle element. Therefore wecan eliminate the first half of the sequence from our search and simply repeat the searchin the exact same manner on the remaining half of the sequence. If, however, the value weare searching for comes before the middle element, then we repeat the search on the first halfof 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

$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 numberof comparisons required to locate some element $y$ in $L$. Since half of the list is eliminatedwith each comparison, there can be no more than ${\log }_{2}n$ comparisons before either the positionsof all the $y$ elements are found or the entire list is eliminated and $y$ is determined to not existin $L$.Thus the worst-case runtime complexity of the binary search is $𝒪(\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 locatedwith 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