Binary search

Binary search is an algorithm which quickly locates an entry with a given value in a sorted array, or determines that no such entry exists, by taking advantage of the sorted precondition of the array. Binary search is much faster than linear search, which simply checks each entry of the array in order, although linear search works when the array is not sorted.

Without loss of generality, assume that the array is sorted in ascending order. Initially, the range in consideration is the entire array. Consider the midpoint of the valid array indices, usually taken to be the floor of the arithmetic mean of the two endpoints. If the entry at the midpoint has the desired value, then the midpoint is the result and the method terminates. If the value of the entry at the midpoint is greater than the desired value, then it and all entries with greater indices are eliminated. If the value of the entry at the midpoint is less than the desired value, then it and all entries with lesser indices are eliminated.

To find the value $c$ in an array $A$ with indices $k$ through $n$ , the binary search algorithm can be summarized by the following cases:

If at any point $k > n$ , then $c$ is not in $A$ .

Otherwise, let $m = \left \lfloor \frac{k + n}{2} \right \rfloor$ .

If $a_m = c$ , return $m$ as the result.
If $a_m > c$ , search $A$ again, replacing $n$ with $m - 1$ .
If $a_m < c$ , search $A$ again, replacing $k$ with $m + 1$ .

Page

Toolbox

Search

Binary search