Binary search algorithm

Binary search algorithm

Visualization of the binary search algorithm where 7 is the target value
Class	Search algorithm
Data structure	Array
Worst-case performance	O(log n)
Best-case performance	O(1)
Average performance	O(log n)
Worst-case space complexity	O(1)

Algorithm

Procedure

Given an array ${\displaystyle A}$ of ${\displaystyle n}$ elements with values or records ${\displaystyle A_{0},A_{1},A_{2},\ldots ,A_{n-1}}$sorted such that ${\displaystyle A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}}$, and target value ${\displaystyle T}$, the following subroutine uses binary search to find the index of ${\displaystyle T}$ in ${\displaystyle A}$.^[7]

1. Set ${\displaystyle L}$ to ${\displaystyle 0}$ and ${\displaystyle R}$ to ${\displaystyle n-1}$.
2. If ${\displaystyle L>R}$, the search terminates as unsuccessful.
3. Set ${\displaystyle m}$ (the position of the middle element) to the floor of ${\displaystyle {\frac {L+R}{2}}}$, which is the greatest integer less than or equal to ${\displaystyle {\frac {L+R}{2}}}$.
4. If ${\displaystyle A_{m}<T}$, set ${\displaystyle L}$ to ${\displaystyle m+1}$ and go to step 2.
5. If ${\displaystyle A_{m}>T}$, set ${\displaystyle R}$ to ${\displaystyle m-1}$ and go to step 2.
6. Now ${\displaystyle A_{m}=T}$, the search is done; return ${\displaystyle m}$.

This iterative procedure keeps track of the search boundaries with the two variables ${\displaystyle L}$ and ${\displaystyle R}$. The procedure may be expressed in pseudocode as follows, where the variable names and types remain the same as above, floor is the floor function, and unsuccessful refers to a specific value that conveys the failure of the search.^[7]

function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else if A[m] > T:
            R := m - 1
        else:
            return m
    return unsuccessful

Alternative procedure

In the above procedure, the algorithm checks whether the middle element (${\displaystyle m}$) is equal to the target (${\displaystyle T}$) in every iteration. Some implementations leave out this check during each iteration. The algorithm would perform this check only when one element is left (when ${\displaystyle L=R}$). This results in a faster comparison loop, as one comparison is eliminated per iteration. However, it requires one more iteration on average.^[8]

1. Set ${\displaystyle L}$ to ${\displaystyle 0}$ and ${\displaystyle R}$ to ${\displaystyle n-1}$.
2. If ${\displaystyle L=R}$, go to step 6.
3. Set ${\displaystyle m}$ (the position of the middle element) to the ceiling of ${\displaystyle {\frac {L+R}{2}}}$, which is the least integer greater than or equal to ${\displaystyle {\frac {L+R}{2}}}$.
4. If ${\displaystyle A_{m}>T}$, set ${\displaystyle R}$ to ${\displaystyle m-1}$ and go to step 2.
5. Set ${\displaystyle L}$ to ${\displaystyle m}$ and go to step 2.
6. Now ${\displaystyle L=R}$, the search is done. If ${\displaystyle A_{L}=T}$, return ${\displaystyle L}$. Otherwise, the search terminates as unsuccessful.

Duplicate elements

The procedure may return any index whose element is equal to the target value, even if there are duplicate elements in the array. For example, if the array to be searched was ${\displaystyle [1,2,3,4,4,5,6,7]}$ and the target was ${\displaystyle 4}$, then it would be correct for the algorithm to either return the 4th (index 3) or 5th (index 4) element. The regular procedure would return the 4th element (index 3). However, it is sometimes necessary to find the leftmost element or the rightmost element if the target value is duplicated in the array. In the above example, the 4th element is the leftmost element of the value 4, while the 5th element is the rightmost element of the value 4. The alternative procedure above will always return the index of the rightmost element if an element is duplicated in the array.^[9]

Procedure for finding the leftmost element

1. Set ${\displaystyle L}$ to ${\displaystyle 0}$ and ${\displaystyle R}$ to ${\displaystyle n}$.
2. If ${\displaystyle L\geq R}$, go to step 6.
3. Set ${\displaystyle m}$ (the position of the middle element) to the floor of ${\displaystyle {\frac {L+R}{2}}}$, which is the greatest integer less than or equal to ${\displaystyle {\frac {L+R}{2}}}$
4. If ${\displaystyle A_{m}<T}$, set ${\displaystyle L}$ to ${\displaystyle m+1}$ and go to step 2.
5. Otherwise, if ${\displaystyle A_{m}\geq T}$, set ${\displaystyle R}$ to ${\displaystyle m}$ and go to step 2.
6. Now ${\displaystyle L=R}$, the search is done, return ${\displaystyle L}$.

If ${\displaystyle L<n}$ and ${\displaystyle A_{L}=T}$, then ${\displaystyle A_{L}}$ is the leftmost element that equals ${\displaystyle T}$. Even if ${\displaystyle T}$ is not in the array, ${\displaystyle L}$ is the rank of ${\displaystyle T}$ in the array, or the number of elements in the array that are less than ${\displaystyle T}$.

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

Procedure for finding the rightmost element

1. Set ${\displaystyle L}$ to ${\displaystyle 0}$ and ${\displaystyle R}$ to ${\displaystyle n}$.
2. If ${\displaystyle L\geq R}$, go to step 6.
3. Set ${\displaystyle m}$ (the position of the middle element) to the floor of ${\displaystyle {\frac {L+R}{2}}}$, which is the greatest integer less than or equal to ${\displaystyle {\frac {L+R}{2}}}$.
4. If ${\displaystyle A_{m}\leq T}$, set ${\displaystyle L}$ to ${\displaystyle m+1}$ and go to step 2.
5. Otherwise, If ${\displaystyle A_{m}>T}$, set ${\displaystyle R}$ to ${\displaystyle m}$ and go to step 2.
6. Now ${\displaystyle L=R}$, the search is done, return ${\displaystyle L-1}$.

If ${\displaystyle L>0}$ and ${\displaystyle A_{L-1}=T}$, then ${\displaystyle A_{L-1}}$ is the rightmost element that equals ${\displaystyle T}$. Even if ${\displaystyle T}$ is not in the array, ${\displaystyle (n-1)-L}$ is the number of elements in the array that are greater than ${\displaystyle T}$.

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] <= T:
            L := m + 1 
        else:
            R := m
    return L - 1

Approximate matches

Binary search can be adapted to compute approximate matches. In the example above, the rank, predecessor, successor, and nearest neighbor are shown for the target value ${\displaystyle 5}$, which is not in the array.

• Rank queries can be performed with the procedure for finding the leftmost element. The number of elements less than the target value is returned by the procedure.^[11]
• Predecessor queries can be performed with rank queries. If the rank of the target value is ${\displaystyle r}$, its predecessor is ${\displaystyle r-1}$.^[12]
• For successor queries, the procedure for finding the rightmost element can be used. If the result of running the procedure for the target value is ${\displaystyle r}$, then the successor of the target value is ${\displaystyle r+1}$.^[12]
• The nearest neighbor of the target value is either its predecessor or successor, whichever is closer.
• Range queries are also straightforward.^[12] Once the ranks of the two values are known, the number of elements greater than or equal to the first value and less than the second is the difference of the two ranks. This count can be adjusted up or down by one according to whether the endpoints of the range should be considered to be part of the range and whether the array contains keys matching those endpoints.^[13]

Performance

A tree representing binary search. The array being searched here is ${\displaystyle [20,30,40,50,80,90,100]}$, and the target value is ${\displaystyle 40}$.

The worst case is reached when the search reaches the deepest level of the tree, while the best case is reached when the target value is the middle element.

In the worst case, binary search makes ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ iterations of the comparison loop, where the ${\textstyle \lfloor \ \rfloor }$ notation denotes the floor function that yields the greatest integer less than or equal to the argument, and ${\textstyle \log _{2}}$ is the binary logarithm. The worst case is reached when the search reaches the deepest level of the tree. This is equivalent to a binary search that has reduced to one element and always eliminates the smaller subarray out of the two in each iteration if they are not of equal size.^[a][14]

The worst case may also be reached when the target element is not in the array. If ${\textstyle n}$ is one less than a power of two, then this is always the case. Otherwise, the search may perform ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$iterations if the search reaches the deepest level of the tree. However, it may make ${\textstyle \lfloor \log _{2}(n)\rfloor }$ iterations, which is one less than the worst case, if the search ends at the second-deepest level of the tree.^[15]

On average, assuming that each element is equally likely to be searched, binary search makes ${\displaystyle \lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n}$ iterations when the target element is in the array. This is approximately equal to ${\displaystyle \log _{2}(n)-1}$ iterations. When the target element is not in the array, binary search makes ${\displaystyle \lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)}$ iterations on average, assuming that the range between and outside elements is equally likely to be searched.^[14]

Performance of alternative procedure

Each iteration of the binary search procedure defined above makes one or two comparisons, checking if the middle element is equal to the target in each iteration. Assuming that each element is equally likely to be searched, each iteration makes 1.5 comparisons on average. A variation of the algorithm checks whether the middle element is equal to the target at the end of the search. On average, this eliminates half a comparison from each iteration. This slightly cuts the time taken per iteration on most computers. However, it guarantees that the search takes the maximum number of iterations, on average adding one iteration to the search. Because the comparison loop is performed only ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ times in the worst case, the slight increase in efficiency per iteration does not compensate for the extra iteration for all but enormous ${\textstyle n}$.^[c][17][18]

Binary search versus other schemes

Sorted arrays with binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval, taking ${\textstyle O(n)}$ time for each such operation. In addition, sorted arrays can complicate memory use especially when elements are often inserted into the array.^[19] There are other data structures that support much more efficient insertion and deletion. Binary search can be used to perform exact matching and set membership (determining whether a target value is in a collection of values). There are data structures that support faster exact matching and set membership. However, unlike many other searching schemes, binary search can be used for efficient approximate matching, usually performing such matches in ${\textstyle O(\log n)}$ time regardless of the type or structure of the values themselves.^[20] In addition, there are some operations, like finding the smallest and largest element, that can be performed efficiently on a sorted array.^[11]

Hashing

Trees

Binary search trees are searched using an algorithm similar to binary search.

However, binary search is usually more efficient for searching as binary search trees will most likely be imperfectly balanced, resulting in slightly worse performance than binary search. This even applies to balanced binary search trees, binary search trees that balance their own nodes, because they rarely produce optimally-balanced trees. Although unlikely, the tree may be severely imbalanced with few internal nodes with two children, resulting in the average and worst-case search time approaching ${\textstyle n}$ comparisons.^[e] Binary search trees take more space than sorted arrays.^[27]

Linear search

Linear search is a simple search algorithm that checks every record until it finds the target value. Linear search can be done on a linked list, which allows for faster insertion and deletion than an array. Binary search is faster than linear search for sorted arrays except if the array is short, although the array needs to be sorted beforehand.^[f][31] All sorting algorithms based on comparing elements, such as quicksort and merge sort, require at least ${\textstyle O(n\log n)}$ comparisons in the worst case.^[32]Unlike linear search, binary search can be used for efficient approximate matching. There are operations such as finding the smallest and largest element that can be done efficiently on a sorted array but not on an unsorted array.^[33]

Set membership algorithms

A related problem to search is set membership. Any algorithm that does lookup, like binary search, can also be used for set membership. There are other algorithms that are more specifically suited for set membership. A bit array is the simplest, useful when the range of keys is limited. It compactly stores a collection of bits, with each bit representing a single key within the range of keys. Bit arrays are very fast, requiring only ${\textstyle O(1)}$ time.^[34] The Judy1 type of Judy array handles 64-bit keys efficiently.^[35]

For approximate results, Bloom filters, another probabilistic data structure based on hashing, store a set of keys by encoding the keys using a bit array and multiple hash functions. Bloom filters are much more space-efficient than bit arrays in most cases and not much slower: with ${\textstyle k}$ hash functions, membership queries require only ${\textstyle O(k)}$ time. However, Bloom filters suffer from false positives.^[g][h][37]

Other data structures

Variations

Uniform binary search

Uniform binary search stores the difference between the current and the two next possible middle elements instead of specific bounds.

Uniform binary search stores, instead of the lower and upper bounds, the index of the middle element and the change in the middle element from the current iteration to the next iteration. Each step reduces the change by about half. For example, if the array to be searched is ${\displaystyle [1,2,3,4,5,6,7,8,9,10,11]}$, the middle element would be ${\displaystyle 6}$. Uniform binary search works on the basis that the difference between the index of middle element of the array and the left and right subarrays is the same. In this case, the middle element of the left subarray (${\displaystyle [1,2,3,4,5]}$) is ${\displaystyle 3}$ and the middle element of the right subarray (${\displaystyle [7,8,9,10,11]}$) is ${\displaystyle 9}$. Uniform binary search would store the value of ${\displaystyle 3}$ as both indices differ from ${\displaystyle 6}$ by this same amount.^[38] To reduce the search space, the algorithm either adds or subtracts this change from the middle element. The main advantage of uniform binary search is that the procedure can store a table of the differences between indices for each iteration of the procedure. Uniform binary search may be faster on systems where it is inefficient to calculate the midpoint, such as on decimal computers.^[39]

Exponential search

Visualization of exponential searching finding the upper bound for the subsequent binary search

Exponential search extends binary search to unbounded lists. It starts by finding the first element with an index that is both a power of two and greater than the target value. Afterwards, it sets that index as the upper bound, and switches to binary search. A search takes ${\textstyle \lfloor \log _{2}x+1\rfloor }$ iterations of the exponential search and at most ${\textstyle \lfloor \log _{2}x\rfloor }$ iterations of the binary search, where ${\textstyle x}$ is the position of the target value. Exponential search works on bounded lists, but becomes an improvement over binary search only if the target value lies near the beginning of the array.^[40]

Interpolation search

Visualization of interpolation search. In this case, no searching is needed because the estimate of the target's location within the array is correct. Other implementations may specify another function for estimating the target's location.

Instead of calculating the midpoint, interpolation search estimates the position of the target value, taking into account the lowest and highest elements in the array as well as length of the array. This is only possible if the array elements are numbers. It works on the basis that the midpoint is not the best guess in many cases. For example, if the target value is close to the highest element in the array, it is likely to be located near the end of the array.^[41] When the distribution of the array elements is uniform or near uniform, it makes ${\textstyle O(\log \log n)}$ comparisons.^[41][42][43]

Fractional cascading

In fractional cascading, each array has pointers to every second element of another array, so only one binary search has to be performed to search all the arrays.

Fractional cascading is a technique that speeds up binary searches for the same element in multiple sorted arrays. Searching each array separately requires ${\textstyle O(k\log n)}$ time, where ${\textstyle k}$ is the number of arrays. Fractional cascading reduces this to ${\textstyle O(k+\log n)}$ by storing specific information in each array about each element and its position in the other arrays.^[44][45]

Noisy binary search

In noisy binary search, there is a certain probability that a comparison is incorrect.

Quantum binary search

Classical computers are bounded to the worst case of exactly ${\textstyle \lfloor \log _{2}n+1\rfloor }$ iterations when performing binary search. Quantum algorithms for binary search are still bounded to a proportion of ${\textstyle \log _{2}n}$ queries (representing iterations of the classical procedure), but the constant factor is less than one, providing for faster performance on quantum computers. Any exact quantum binary search procedure—that is, a procedure that always yields the correct result—requires at least ${\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.220\log _{2}n}$ queries in the worst case, where ${\textstyle \ln }$ is the natural logarithm.^[51] There is an exact quantum binary search procedure that runs in ${\textstyle 4\log _{605}n\approx 0.433\log _{2}n}$ queries in the worst case.^[52] In comparison, Grover's algorithm is the optimal quantum algorithm for searching an unordered list of elements, and it requires ${\displaystyle O({\sqrt {n}})}$ queries.^[53]

History

Implementation issues

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky ... — Donald Knuth^[2]

In a practical implementation, the variables used to represent the indices will often be of fixed size, and this can result in an arithmetic overflow for very large arrays. If the midpoint of the span is calculated as ${\displaystyle {\frac {L+R}{2}}}$, then the value of ${\displaystyle L+R}$ may exceed the range of integers of the data type used to store the midpoint, even if ${\displaystyle L}$ and ${\displaystyle R}$ are within the range. If ${\displaystyle L}$ and ${\displaystyle R}$ are nonnegative, this can be avoided by calculating the midpoint as ${\displaystyle L+{\frac {R-L}{2}}}$.^[62]

If the target value is greater than the greatest value in the array, and the last index of the array is the maximum representable value of ${\displaystyle L}$, the value of ${\displaystyle L}$ will eventually become too large and overflow. A similar problem will occur if the target value is smaller than the least value in the array and the first index of the array is the smallest representable value of ${\displaystyle R}$. In particular, this means that ${\displaystyle R}$ must not be an unsigned type if the array starts with index ${\displaystyle 0}$.^[60][62]

An infinite loop may occur if the exit conditions for the loop are not defined correctly. Once ${\displaystyle L}$ exceeds ${\displaystyle R}$, the search has failed and must convey the failure of the search. In addition, the loop must be exited when the target element is found, or in the case of an implementation where this check is moved to the end, checks for whether the search was successful or failed at the end must be in place. Bentley found that most of the programmers who incorrectly implemented binary search made an error in defining the exit conditions.^[8][63]

Library support

• C provides the function bsearch() in its standard library, which is typically implemented via binary search, although the official standard does not require it so.^[64]
• C++'s Standard Template Library provides the functions binary_search(), lower_bound(), upper_bound() and equal_range().^[65]
• COBOL provides the SEARCH ALL verb for performing binary searches on COBOL ordered tables.^[66]
• Go's sort standard library package contains the functions Search, SearchInts, SearchFloat64s, and SearchStrings, which implement general binary search, as well as specific implementations for searching slices of integers, floating-point numbers, and strings, respectively.^[67]
• Java offers a set of overloaded binarySearch() static methods in the classes Arrays and Collections in the standard java.util package for performing binary searches on Java arrays and on Lists, respectively.^[68][69]
• Microsoft's .NET Framework 2.0 offers static generic versions of the binary search algorithm in its collection base classes. An example would be System.Array's method BinarySearch<T>(T[] array, T value).^[70]
• For Objective-C, the Cocoa framework provides the NSArray -indexOfObject:inSortedRange:options:usingComparator: method in Mac OS X 10.6+.^[71]Apple's Core Foundation C framework also contains a CFArrayBSearchValues() function.^[72]
• Python provides the bisect module.^[73]
• Ruby's Array class includes a bsearch method with built-in approximate matching.^[74]