使用者:深鳴/二分搜尋演算法

  此頁面介紹的是搜尋有限有序陣列中特定值位置的演算法。關於計算連續函式中特定值位置的方法，請見「二分法 (數學)」。

深鳴/二分搜尋演算法
二分搜尋過程示意，目標值為7
概況
類別	搜尋演算法
資料結構	陣列
複雜度
平均時間複雜度	$O(\log n)$
最壞時間複雜度	$O(\log n)$
最佳時間複雜度	$O(1)$
空間複雜度	$O(1)$
最佳解	是
相關變數的定義

二分搜尋（英語：binary search，中國大陸作二分查找，大陸又作二分搜索）是用於搜尋有序陣列中目標值位置的搜尋演算法。

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.

演算法

二分搜尋適用於有序陣列。二分搜尋首先比較陣列中間的元素與目標值。如果目標值與該元素匹配，則返回該元素在陣列中的位置；如果目標值小於該元素，則在陣列較小的那一半中繼續搜尋；如果目標值大於該元素，則在陣列較大的那一半中繼續搜尋。通過這種方法，每次疊代都能將搜尋範圍縮小一半。

過程

給定一個包含$n$個元素的陣列$A$，其中的值或記錄分別為$A_{0},A_{1},A_{2},\ldots ,A_{n-1}$，且滿足$A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}$。假設目標值為$T$。下面的子程式使用二分搜尋來尋找$T$在陣列$A$中的索引。

1. 取$L$為$0$，$R$為$n-1$。
2. 如果$L>R$，則搜尋失敗並終止。
3. 取$m$（中間元素的位置）為${\frac {L+R}{2}}$的向下取整值，即不大於${\frac {L+R}{2}}$的最大整數。
4. 如果$A_{m}<T$，則取$L$為$m+1$，並返回步驟2。
5. 如果$A_{m}>T$，則取$R$為$m-1$，並返回步驟2。
6. 如果$A_{m}=T$，則搜尋完成，返回$m$。

這個疊代過程使用兩個變數$L$和$R$來跟蹤搜尋邊界。該過程可以用虛擬碼表示如下，其中變數名和類型與上文相同，floor為下取整函式，unsuccessful表示搜尋失敗時的特定返回值：

二分搜尋過程

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

也可取$m$為${\frac {L+R}{2}}$的向上取整值。如此所做，若目標值在陣列中出現多次，結果可能會有所不同。

替代過程

上述過程中，每次疊代都會檢查中間元素（$m$）是否等於目標值（$T$）。而在其他一些實現中，僅剩下一個元素（即$L=R$）時，才會執行這項檢查，這樣每次疊代時就無需檢查。這種方式的比較迴圈更快，因為每次疊代少了一次比較，但平均只需要多一次疊代。

赫爾曼·博滕布魯赫於1962年首次發表了省略此檢查的實現。

1. 取$L$為$0$，$R$為$n-1$。
2. 當$L\neq R$時，
   1. 取$m$（中間元素的位置）為${\frac {L+R}{2}}$的向上取整值，即不小於${\frac {L+R}{2}}$的最小整數。
   2. 如果$A_{m}>T$，取$R$為$m-1$。
   3. 否則說明$A_{m}\leq T$，取$L$為$m$。
3. 現在$L=R$，搜尋完成。如果$A_{L}=T$，返回$L$。否則，搜尋失敗並終止。

該版本的虛擬碼如下，其中ceil是上取整函式：

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m − 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

重複元素

即使陣列中存在重複元素，演算法可能返回任意一個與目標值相等的索引。例如，如果要搜尋的陣列為$[1,2,3,4,4,5,6,7]$，且目標值為$4$，那麼演算法返回第4個（索引為 3）或第5個（索引為4）元素都是正確的。常規過程通常返回第4個元素（索引為3），但並不總是返回第一個重複項（考慮陣列$[1,2,4,4,4,5,6,7]$，這時依然返回第4個元素）。然而，有時需要找到目標值在陣列中重複出現的最左側或最右側的元素。在上述例子中，第4個元素是值為4的最左側元素，而第5個元素是值為4的最右側元素。上述的替代過程總是會返回最右側元素的索引（如果該元素存在的話）。

搜尋最左側元素的過程

要搜尋最左邊的元素，可以使用以下過程：

1. 取$L$為$0$，$R$為$n$。
2. 當$L<R$時，
   1. 取$m$（中間元素的位置）為${\frac {L+R}{2}}$的向下取整值，即不大於${\frac {L+R}{2}}$的最大整數。
   2. 如果$A_{m}<T$，取$L$為$m+1$。
   3. 否則說明$A_{m}\geq T$，取$R$為$m$。
3. 返回$L$。

如果$L<n$且$A_{L}=T$，那麼$A_{L}$是等於$T$的最左側元素。即使$T$不在陣列中，$L$也是$T$在陣列中的排序位置，即陣列中小於$T$的元素數量。

該版本的虛擬碼如下，其中floor是下取整函式：

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

搜尋最右側元素的過程

要搜尋最左邊的元素，可以使用以下過程：

1. 取$L$為$0$，$R$為$n$。
2. 當$L<R$時，
   1. 取$m$（中間元素的位置）為${\frac {L+R}{2}}$的向下取整值，即不大於${\frac {L+R}{2}}$的最大整數。
   2. 如果$A_{m}>T$，取$R$為$m$。
   3. 否則說明$A_{m}\leq T$，取$L$為$m+1$。
3. 返回$R-1$。

如果$R>0$ 且$A_{R-1}=T$，那麼$A_{R-1}$是等於$T$的最右側元素。即使$T$不在陣列中，$n-R$也是陣列中大於$T$的元素數量。

該版本的虛擬碼如下，其中floor是下取整函式：

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

近似匹配

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 $5$, which is not in the array.

上述過程僅用於精確匹配，即找到目標值的位置。然而，由於二分搜尋在有序陣列上進行，所以很容易擴充它以執行近似匹配。例如，二分搜尋可以用來計算給定值的排序位置（即比它小的元素的數量）、前驅（前一個較小的元素）、後繼（下一個較大的元素）、最近鄰。範圍查詢（搜尋兩個值之間的元素數量）可以通過查詢兩次排序位置來完成。

• 查詢排序位置可以使用搜尋最左側元素的過程來完成。程式的返回值即為小於目標值的元素數量。
• Predecessor queries can be performed with rank queries. If the rank of the target value is $r$, its predecessor is $r-1$.
• 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 $r$, then the successor of the target value is $r+1$.
• The nearest neighbor of the target value is either its predecessor or successor, whichever is closer.
• Range queries are also straightforward. 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 entries matching those endpoints.

效能

A tree representing binary search. The array being searched here is $[20,30,40,50,80,90,100]$, and the target value is $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 terms of the number of comparisons, the performance of binary search can be analyzed by viewing the run of the procedure on a binary tree. The root node of the tree is the middle element of the array. The middle element of the lower half is the left child node of the root, and the middle element of the upper half is the right child node of the root. The rest of the tree is built in a similar fashion. Starting from the root node, the left or right subtrees are traversed depending on whether the target value is less or more than the node under consideration.

In the worst case, binary search makes ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ iterations of the comparison loop, where the ${\textstyle \lfloor \cdot \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. This is because the worst case is reached when the search reaches the deepest level of the tree, and there are always ${\textstyle \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 ${\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.

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.

空間複雜度

Binary search requires three pointers to elements, which may be array indices or pointers to memory locations, regardless of the size of the array. Therefore, the space complexity of binary search is $O(1)$ in the word RAM model of computation.

平均情況的推導

The average number of iterations performed by binary search depends on the probability of each element being searched. The average case is different for successful searches and unsuccessful searches. It will be assumed that each element is equally likely to be searched for successful searches. For unsuccessful searches, it will be assumed that the intervals between and outside elements are equally likely to be searched. The average case for successful searches is the number of iterations required to search every element exactly once, divided by $n$, the number of elements. The average case for unsuccessful searches is the number of iterations required to search an element within every interval exactly once, divided by the $n+1$ intervals.

成功的搜尋

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 $l$, 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 $n$ 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 $n$ 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 $n$, 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 $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 ${\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 very large ${\textstyle n}$.

執行時間和快取使用

In analyzing the performance of binary search, another consideration is the time required to compare two elements. For integers and strings, the time required increases linearly as the encoding length (usually the number of bits) of the elements increase. For example, comparing a pair of 64-bit unsigned integers would require comparing up to double the bits as comparing a pair of 32-bit unsigned integers. The worst case is achieved when the integers are equal. This can be significant when the encoding lengths of the elements are large, such as with large integer types or long strings, which makes comparing elements expensive. Furthermore, comparing floating-point values (the most common digital representation of real numbers) is often more expensive than comparing integers or short strings.

On most computer architectures, the processor has a hardware cache separate from RAM. Since they are located within the processor itself, caches are much faster to access but usually store much less data than RAM. Therefore, most processors store memory locations that have been accessed recently, along with memory locations close to it. For example, when an array element is accessed, the element itself may be stored along with the elements that are stored close to it in RAM, making it faster to sequentially access array elements that are close in index to each other (locality of reference). On a sorted array, binary search can jump to distant memory locations if the array is large, unlike algorithms (such as linear search and linear probing in hash tables) which access elements in sequence. This adds slightly to the running time of binary search for large arrays on most systems.

二分搜尋與其他方案

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

二元樹

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

A binary search tree is a binary tree data structure that works based on the principle of binary search. The records of the tree are arranged in sorted order, and each record in the tree can be searched using an algorithm similar to binary search, taking on average logarithmic time. Insertion and deletion also require on average logarithmic time in binary search trees. This can be faster than the linear time insertion and deletion of sorted arrays, and binary trees retain the ability to perform all the operations possible on a sorted array, including range and approximate queries.

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 ${\textstyle 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.

雜湊表

For implementing associative arrays, hash tables, a data structure that maps keys to records using a hash function, are generally faster than binary search on a sorted array of records. Most hash table implementations require only amortized constant time on average. However, hashing is not useful for approximate matches, such as computing the next-smallest, next-largest, and nearest key, as the only information given on a failed search is that the target is not present in any record. Binary search is ideal for such matches, performing them in logarithmic time. Binary search also supports approximate matches. Some operations, like finding the smallest and largest element, can be done efficiently on sorted arrays but not on hash tables.

集合

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. 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 ${\textstyle k}$ hash functions, membership queries require only ${\textstyle O(k)}$ time. However, Bloom filters suffer from false positives.

其他資料結構

There exist data structures that may improve on binary search in some cases for both searching and other operations available for sorted arrays. For example, searches, approximate matches, and the operations available to sorted arrays can be performed more efficiently than binary search on specialized data structures such as van Emde Boas trees, fusion trees, tries, and bit arrays. These specialized data structures are usually only faster because they take advantage of the properties of keys with a certain attribute (usually keys that are small integers), and thus will be time or space consuming for keys that lack that attribute. As long as the keys can be ordered, these operations can always be done at least efficiently on a sorted array regardless of the keys. Some structures, such as Judy arrays, use a combination of approaches to mitigate this while retaining efficiency and the ability to perform approximate matching.

其他形式

統一二分搜尋

主條目：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 difference in the index of the middle element from the current iteration to the next iteration. A lookup table containing the differences is computed beforehand. For example, if the array to be searched is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], the middle element ($m$) would be 6. In this case, the middle element of the left subarray ([1, 2, 3, 4, 5]) is 3 and the middle element of the right subarray ([7, 8, 9, 10, 11]) is 9. Uniform binary search would store the value of 3 as both indices differ from 6 by this same amount. To reduce the search space, the algorithm either adds or subtracts this change from the index of the middle element. Uniform binary search may be faster on systems where it is inefficient to calculate the midpoint, such as on decimal computers.

指數搜尋

主條目：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 before binary search is started 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.

插值搜尋

主條目：插值搜尋

Visualization of interpolation search using linear interpolation. 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. 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.

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 ${\textstyle 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

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.

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.

推廣到圖表

Binary search has been generalized to work on certain types of graphs, where the target value is stored in a vertex instead of an array element. Binary search trees are one such generalization—when a vertex (node) in the tree is queried, the algorithm either learns that the vertex is the target, or otherwise which subtree the target would be located in. However, this can be further generalized as follows: given an undirected, positively weighted graph and a target vertex, the algorithm learns upon querying a vertex that it is equal to the target, or it is given an incident edge that is on the shortest path from the queried vertex to the target. The standard binary search algorithm is simply the case where the graph is a path. Similarly, binary search trees are the case where the edges to the left or right subtrees are given when the queried vertex is unequal to the target. For all undirected, positively weighted graphs, there is an algorithm that finds the target vertex in $O(\log n)$ queries in the worst case.

嘈雜二分搜尋

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

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 ${\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 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 ${\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}$ queries in the worst case, where ${\textstyle \ln }$ is the natural logarithm. 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. In comparison, Grover's algorithm is the optimal quantum algorithm for searching an unordered list of elements, and it requires $O({\sqrt {n}})$ queries.

歷史

The idea of sorting a list of items to allow for faster searching dates back to antiquity. The earliest known example was the Inakibit-Anu tablet from Babylon dating back to 約200 BCE. The tablet contained about 500 sexagesimal numbers and their reciprocals sorted in lexicographical order, which made searching for a specific entry easier. In addition, several lists of names that were sorted by their first letter were discovered on the Aegean Islands. Catholicon, a Latin dictionary finished in 1286 CE, was the first work to describe rules for sorting words into alphabetical order, as opposed to just the first few letters.

In 1946, John Mauchly made the first mention of binary search as part of the Moore School Lectures, a seminal and foundational college course in computing. In 1957, William Wesley Peterson published the first method for interpolation search. Every published binary search algorithm worked only for arrays whose length is one less than a power of two until 1960, when Derrick Henry Lehmer published a binary search algorithm that worked on all arrays. In 1962, Hermann Bottenbruch presented an ALGOL 60 implementation of binary search that placed the comparison for equality at the end, increasing the average number of iterations by one, but reducing to one the number of comparisons per iteration. The uniform binary search was developed by A. K. Chandra of Stanford University in 1971. In 1986, Bernard Chazelle and Leonidas J. Guibas introduced fractional cascading as a method to solve numerous search problems in computational geometry.

實現問題

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky

——Donald Knuth

When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases. A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks. Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years. The Java programming language library implementation of binary search had the same overflow bug for more than nine years.

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

An infinite loop may occur if the exit conditions for the loop are not defined correctly. Once $L$ exceeds $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.

庫支援

Many languages' standard libraries include binary search routines:

• 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.
• C++'s standard library provides the functions binary_search(), lower_bound(), upper_bound() and equal_range().
• D's standard library Phobos, in std.range module provides a type SortedRange (returned by sort() and assumeSorted() functions) with methods contains(), equaleRange(), lowerBound() and trisect(), that use binary search techniques by default for ranges that offer random access.
• COBOL provides the SEARCH ALL verb for performing binary searches on COBOL ordered tables.
• 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.
• 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.
• 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).
• For Objective-C, the Cocoa framework provides the NSArray -indexOfObject:inSortedRange:options:usingComparator: method in Mac OS X 10.6+. Apple's Core Foundation C framework also contains a CFArrayBSearchValues() function.
• Python provides the bisect module that keeps a list in sorted order without having to sort the list after each insertion.
• Ruby's Array class includes a bsearch method with built-in approximate matching.
• Rust's slice primitive provides binary_search(), binary_search_by(), binary_search_by_key(), and partition_point().

參見

• Bisection method – the same idea used to solve equations in the real numbers
• Multiplicative binary search

注釋和參考文獻

來源

• Bentley, Jon. Programming pearls 2nd. Addison-Wesley. 2000. ISBN 978-0-201-65788-3 （英語）. 
• Butterfield, Andrew; Ngondi, Gerard E. A dictionary of computer science 7th. Oxford, UK: Oxford University Press. 2016. ISBN 978-0-19-968897-5 （英語）. 
• Chang, Shi-Kuo. Data structures and algorithms. Software Engineering and Knowledge Engineering 13. Singapore: World Scientific. 2003. ISBN 978-981-238-348-8 （英語）. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to algorithms 3rd. MIT Press and McGraw-Hill. 2009. ISBN 978-0-262-03384-8 （英語）. 
• Fitzgerald, Michael. Ruby pocket reference. Sebastopol, California: O'Reilly Media. 2015. ISBN 978-1-4919-2601-7 （英語）. 
• Goldman, Sally A.; Goldman, Kenneth J. A practical guide to data structures and algorithms using Java. Boca Raton, Florida: CRC Press. 2008. ISBN 978-1-58488-455-2 （英語）. 
• Kasahara, Masahiro; Morishita, Shinichi. Large-scale genome sequence processing. London, UK: Imperial College Press. 2006. ISBN 978-1-86094-635-6 （英語）. 
• Knuth, Donald. Fundamental algorithms. The Art of Computer Programming 1 3rd. Reading, MA: Addison-Wesley Professional. 1997. ISBN 978-0-201-89683-1 （英語）. 
• Knuth, Donald. Sorting and searching. The Art of Computer Programming 3 2nd. Reading, MA: Addison-Wesley Professional. 1998. ISBN 978-0-201-89685-5 （英語）. 
• Knuth, Donald. Combinatorial algorithms. The Art of Computer Programming 4A 1st. Reading, MA: Addison-Wesley Professional. 2011. ISBN 978-0-201-03804-0 （英語）. 
• Moffat, Alistair; Turpin, Andrew. Compression and coding algorithms. Hamburg, Germany: Kluwer Academic Publishers. 2002. ISBN 978-0-7923-7668-2. doi:10.1007/978-1-4615-0935-6 （英語）. 
• Sedgewick, Robert; Wayne, Kevin. Algorithms 4th. Upper Saddle River, New Jersey: Addison-Wesley Professional. 2011. ISBN 978-0-321-57351-3 （英語）.  Condensed web version ; book version .
• Sedgewick, Robert; Wayne, Kevin. 算法. 由謝路雲翻譯 第4版. 北京: 人民郵電出版社. 2012. ISBN 978-7-115-29380-0 （中文（中國大陸））. 
• Stroustrup, Bjarne. The C++ programming language 4th. Upper Saddle River, New Jersey: Addison-Wesley Professional. 2013. ISBN 978-0-321-56384-2 （英語）. 

外部連結

• Anthony Lin. Binary search algorithm (PDF). 理學維基期刊. 2019-07-02, 2 (1): 5. ISSN 2470-6345. doi:10.15347/WJS/2019.005. Wikidata Q81434400 （英語）. 。該論文內容取自英語維基百科的對應條目，於2018年經過外部學術同行評審。
• NIST Dictionary of Algorithms and Data Structures: binary search
• Comparisons and benchmarks of a variety of binary search implementations in C 網際網路檔案館的存檔，存檔日期2019-09-25.