Binary search
≈ 20 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.
If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.
Binary search runs in logarithmic time in the worst case, making O(\log n) comparisons, where n is the number of elements in the array. Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search.
There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.
There are numerous variations of binary search. In particular, fractional cascading speeds up binary searches for the same value in multiple arrays.…
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.
If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.
Binary search runs in logarithmic time in the worst case, making O(\log n) comparisons, where n is the number of elements in the array. Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search.
There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.
There are numerous variations of binary search. In particular, fractional cascading speeds up binary searches for the same value in multiple arrays. Fractional cascading efficiently solves a number of search problems in computational geometry and in numerous other fields.
Exponential search extends binary search to unbounded lists. The binary search tree and B-tree data structures are based on binary search.
Now A_m = T , the search is done; return m . This iterative procedure keeps track of the search boundaries with the two variables L and 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. function binary_search(A, n, T) is L := 0 R := n − 1 while L ≤ R do m := L + floor((R - L) / 2) if A[m] T then R := m − 1 else: return m return unsuccessful Alternatively, the algorithm may take the ceiling of \frac{R-L}{2} . This may change the result if the target value appears more than once in the array.
In the above procedure, the algorithm checks whether the middle element ( m ) is equal to the target ( 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 L=R ). This results in a faster comparison loop, as one comparison is eliminated per iteration, while it requires only one more iteration on average. Hermann Bottenbruch published the first implementation to leave out this check in 19621. Set L to 0 and R to n-1 .
While L \neq R , Set m (the position of the middle element) to L plus the ceiling of \frac{R-L}{2} , which is the least integer greater than or equal to \frac{R-L}{2} . If A_m > T , set R to m-1 . Else, A_m \leq T ; set L to m . Now L=R , the search is done.
If A_L=T , return L . Otherwise, the search terminates as unsuccessful. Where ceil is the ceiling function, the pseudocode for this version is: function binary_search_alternative(A, n, T) is L := 0 R := n − 1 while L != R do m := L + ceil((R - L) / 2) if A[m] > T then R := m − 1 else: L := m if A[L] = T then return L return unsuccessful If L and A_L = T , then A_L is the leftmost element that equals T . Even if T is not in the array, L is the rank of T in the array, or the number of elements in the array that are less than T . Where floor is the floor function, the pseudocode for this version is: function binary_search_leftmost(A, n, T): L := 0 R := n while L R > 0 and A_{R-1}=T , then A_{R-1} is the rightmost element that equals T . Even if T is not in the array, n-R is the number of elements in the array that are greater than T . Where floor is the floor function, the pseudocode for this version is: function binary_search_rightmost(A, n, T): L := 0 R := n while L T: R := m else: L := m + 1 return R - 1 In the worst case, binary search makes \lfloor \log_2 (n) + 1 \rfloor iterations of the comparison loop, where the \lfloor\cdot \rfloor notation denotes the floor function that yields the greatest integer less than or equal to the argument, and \log_2 is the binary logarithm.
This is because the worst case is reached when the search reaches the deepest level of the tree, and there are always \lfloor \log_2 (n) + 1 \rfloor levels in the tree for any binary search. The worst case may also be reached when the target element is not in the array. If n is one less than a power of two, then this is always the case.
Otherwise, the search may perform \lfloor \log_2 (n) + 1 \rfloor iterations if the search reaches the deepest level of the tree. However, it may make \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.
On average, assuming that each element is equally likely to be searched, binary search makes \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 \log_2(n) - 1 iterations.
When the target element is not in the array, binary search makes \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. In the best case, where the target value is the middle element of the array, its position is returned after one iteration.
In terms of iterations, no search algorithm that works only by comparing elements can exhibit better average and worst-case performance than binary search. The comparison tree representing binary search has the fewest levels possible as every level above the lowest level of the tree is filled completely.
Otherwise, the search algorithm can eliminate few elements in an iteration, increasing the number of iterations required in the average and worst case. This is the case for other search algorithms based on comparisons, as while they may work faster on some target values, the average performance over all elements is worse than binary search.
By dividing the array in half, binary search ensures that the size of both subarrays are as similar as possible. In the binary tree representation, a successful search can be represented by a path from the root to the target node, called an internal path. The length of a path is the number of edges (connections between nodes) that the path passes through.
The number of iterations performed by a search, given that the corresponding path has length , is l + 1 counting the initial iteration. The internal path length is the sum of the lengths of all unique internal paths. Since there is only one path from the root to any single node, each internal path represents a search for a specific element.
If there are elements, which is a positive integer, and the internal path length is I(n) , then the average number of iterations for a successful search T(n) = 1 + \frac{I(n)}{n} , with the one iteration added to count the initial iteration. Since binary search is the optimal algorithm for searching with comparisons, this problem is reduced to calculating the minimum internal path length of all binary trees with nodes, which is equal to: I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor For example, in a 7-element array, the root requires one iteration, the two elements below the root require two iterations, and the four elements below require three iterations.
In this case, the internal path length is: \sum_{k=1}^7 \left \lfloor \log_2(k) \right \rfloor = 0 + 2(1) + 4(2) = 2 + 8 = 10 The average number of iterations would be 1 + \frac{10}{7} = 2 \frac{3}{7} based on the equation for the average case. The sum for I(n) can be simplified to: I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor = (n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2 Substituting the equation for I(n) into the equation for T(n) : T(n) = 1 + \frac{(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2}{n} = \lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n For integer , this is equivalent to the equation for the average case on a successful search specified above.
Unsuccessful searches can be represented by augmenting the tree with external nodes, which forms an extended binary tree. If an internal node, or a node present in the tree, has fewer than two child nodes, then additional child nodes, called external nodes, are added so that each internal node has two children.
By doing so, an unsuccessful search can be represented as a path to an external node, whose parent is the single element that remains during the last iteration. An external path is a path from the root to an external node. The external path length is the sum of the lengths of all unique external paths.
If there are n elements, which is a positive integer, and the external path length is E(n) , then the average number of iterations for an unsuccessful search is T'(n)=\frac{E(n)}{n+1} , with the one iteration added to count the initial iteration. The external path length is divided by n+1 instead of n because there are n+1 external paths, representing the intervals between and outside the elements of the array.
This problem can similarly be reduced to determining the minimum external path length of all binary trees with n nodes. For all binary trees, the external path length is equal to the internal path length plus 2n . Substituting the equation for I(n) : E(n) = I(n) + 2n = \left[(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2\right] + 2n = (n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1} Substituting the equation for E(n) into the equation for T'(n) , the average case for unsuccessful searches can be determined: T'(n) = \frac{(n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}}{(n+1)} = \lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1) 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 \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 very large n . Sorted arrays with binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval, taking O(n) time for each such operation. In addition, sorted arrays can complicate memory use especially when elements are often inserted into the array.
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 O(\log n) time regardless of the type or structure of the values themselves. In addition, there are some operations, like finding the smallest and largest element, that can be performed efficiently on a sorted array.
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.{{Efn| performed a formal time performance analysis of both of these search algorithms. On Knuth's MIX computer, which Knuth designed as a representation of an ordinary computer, binary search takes on average 18 \log n - 16 units of time for a successful search, while linear search with a sentinel node at the end of the list takes 1.75n + 8.5 - \frac{n \text{ mod } 2}{4n} units.
Linear search has lower initial complexity because it requires minimal computation, but it quickly outgrows binary search in complexity. On the MIX computer, binary search only outperforms linear search with a sentinel if n > 44 . }} All sorting algorithms based on comparing elements, such as quicksort and merge sort, require at least O(n \log n) comparisons in the worst case.
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.
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 the tree with the fewest possible levels.
Except for balanced binary search trees, the tree may be severely imbalanced with few internal nodes with two children, resulting in the average and worst-case search time approaching n comparisons. Binary search trees take more space than sorted arrays.
Binary search trees lend themselves to fast searching in external memory stored in hard disks, as binary search trees can be efficiently structured in filesystems. The B-tree generalizes this method of tree organization. B-trees are frequently used to organize long-term storage such as databases and filesystems.
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 O(1) time.
The Judy1 type of Judy array handles 64-bit keys efficiently. 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 k hash functions, membership queries require only O(k) time. However, Bloom filters suffer from false positives.
Exponential search
ing 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 \lfloor \log_2 x + 1\rfloor iterations before binary search is started and at most \lfloor \log_2 x \rfloor iterations of the binary search, where 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.
A common interpolation function is linear interpolation. If A is the array, L, R are the lower and upper bounds respectively, and T is the target, then the target is estimated to be about (T - A_L) / (A_R - A_L) of the way between L and R . When linear interpolation is used, and the distribution of the array elements is uniform or near uniform, interpolation search makes O(\log \log n) comparisons.
In practice, interpolation search is slower than binary search for small arrays, as interpolation search requires extra computation. Its time complexity grows more slowly than binary search, but this only compensates for the extra computation for large arrays. Fractional cascading is a technique that speeds up binary searches for the same element in multiple sorted arrays.
Searching each array separately requires O(k \log n) time, where k is the number of arrays. Fractional cascading reduces this to O(k + \log n) by storing specific information in each array about each element and its position in the other arrays. Fractional cascading was originally developed to efficiently solve various computational geometry problems.
Fractional cascading has been applied elsewhere, such as in data mining and Internet Protocol routing. Noisy binary search algorithms solve the case where the algorithm cannot reliably compare elements of the array. For each pair of elements, there is a certain probability that the algorithm makes the wrong comparison.
Noisy binary search can find the correct position of the target with a given probability that controls the reliability of the yielded position. Every noisy binary search procedure must make at least (1 - \tau)\frac{\log_2 (n)}{H(p)} - \frac{10}{H(p)} comparisons on average, where H(p) = -p \log_2 (p) - (1 - p) \log_2 (1 - p) is the binary entropy function and \tau is the probability that the procedure yields the wrong position.
The noisy binary search problem can be considered as a case of the Rényi-Ulam game, a variant of Twenty Questions where the answers may be wrong. Classical computers are bounded to the worst case of exactly \lfloor \log_2 n + 1 \rfloor iterations when performing binary search.
Quantum algorithms for binary search are still bounded to a proportion of \log_2 n queries (representing iterations of the classical procedure), but the constant factor is less than one, providing for a lower time complexity on quantum computers. Any exact quantum binary search procedure—that is, a procedure that always yields the correct result—requires at least \frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n queries in the worst case, where \ln is the natural logarithm.
There is an exact quantum binary search procedure that runs in 4 \log_{605} n \approx 0.433 \log_2 n queries in the worst case. In comparison, Grover's algorithm is the optimal quantum algorithm for searching an unordered list of elements, and it requires O(\sqrt{n}) queries.
Classical binary search implicitly treats the target as equally likely to lie anywhere in the search space, and so splits each interval at its midpoint, requiring \lfloor \log_2 n + 1 \rfloor iterations in the worst case. Bayesian binary search (BBS) instead learns a probability density over the search space and splits at the median of that density, bisecting probability mass rather than the interval itself.
Viewed through Bayesian inference, classical binary search is the special case in which the prior is uniform and each comparison is a deterministic likelihood that assigns zero probability to half the remaining interval. BBS generalizes this by replacing the uniform prior with a learned prior P_\text{learned}(x) —estimated by supervised methods such as Gaussian process regression, Bayesian neural networks or quantile regression, or by unsupervised methods such as Gaussian mixture models, kernel density estimation and maximum likelihood estimation—and probing at the point p_k satisfying \int_{a_k}^{p_k} P(x \mid \mathcal{D}_k)\,dx = \tfrac{1}{2} .
The posterior update after each comparison is equivalent to bisection in probability density space
External links
NIST Dictionary of Algorithms and Data Structures: binary search Comparisons and benchmarks of a variety of binary search implementations in C
Text derived from https://en.wikipedia.org/w/index.php?oldid=1376409833 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Binary search” publication date (×1) · confidence 0.95 revision URL