查看“︁Draft:二分搜尋”︁的源代码

{{NoteTA
|G1 = IT
| 1 = zh-cn:查找; zh-tw:搜尋
| 2 = zh-hans:迭代; zh-hant:疊代
}}
{{about|查找有限有序数组中特定值位置的算法|计算连续函数中特定值位置的方法|二分法 (數學)}}
{{Infobox algorithm
|class=[[搜索算法]]
|image = Binary Search Depiction.svg{{skin-invert}}
|caption = 二分查找过程示意，目标值为7
|data = [[数组]]
|time = <math> O(\log n) </math>
|space = <math> O(1) </math>
|best-time = <math> O(1) </math>
|average-time = <math> O(\log n) </math>
|optimal = 是
}}
{{地区用词|cn=二分查找{{sfn|Sedgewick|Wayne|谢路云|2012|loc=§3.1.5 有序数组中的二分查找}}|tw=二分搜尋<ref>{{Cite conference |author=廖永申 |author2=王欣平 |date=2006-06-12 |title=在嵌入式Linux系統上的新一代網路協定轉換軟體開發 |url=http://dspace.fcu.edu.tw/handle/2376/1896 |conference=2003年NCS全國計算機會議 |language=zh-Hant-TW |access-date=2024-07-16}}</ref>|start={{lang-en|binary search}}|end=大陆又作'''二分-{搜索}-'''<ref name="韦纯福">{{cite journal |author=韦纯福 |title=基于分治思想的二分搜索技术研究 |journal=大众科技 |year=2008 |issue=3 |pages=58-59 |id={{CNKI|DZJI200803022|CJFQ|r}} |language=zh-Hans-CN }}</ref>}}{{Efn|又称{{地区用词|cn=折半查找<ref name="骆剑锋">{{cite journal |author=骆剑锋 |title=哈希表与一般查找方法的比较及冲突的解决 |journal=十堰职业技术学院学报 |year=2007 |issue=5 |pages=96-98 |id={{CNKI|SYZJ200705034|CJFQ|r}} |language=zh-Hans-CN }}</ref>|tw=折半搜尋|start={{lang-en|half-interval search}}<ref name="Williams1976">{{Cite conference |last=Williams, Jr. |first=Louis F. |date=1976-04-22 |title=A modification to the half-interval search (binary search) method |conference=Proceedings of the 14th ACM Southeast Conference |publisher=ACM |pages=95–101 |doi=10.1145/503561.503582 |doi-access=free}}</ref>|end=大陆又作'''折半-{搜索}-'''<ref name="王晓东">{{cite journal |author=王晓东 |title= 一种在TQuery记录集中实现快速搜索的方法 |journal=管理信息系统 |year=2000 |issue=3 |pages=56-57 |id={{CNKI|JYXX200003023|CJFQ|r}} |language=zh-Hans-CN }}</ref>，直译为「半区间搜索」}}、'''对数搜索'''（{{lang-en|logarithmic search}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}}），英文中又称{{lang|en|binary chop}}{{Sfn|Butterfield|Ngondi|2016|p=46}}（{{lang|en|chop}}有「劈、斩」之意）。}}是用于查找{{Le|有序数组|Sorted array}}中目标值位置的[[搜索算法]]。{{Sfn|Cormen|Leiserson|Rivest|Stein|2009|p=39}}<ref>{{MathWorld |title=Binary search |id=BinarySearch}}</ref>

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 [[Time complexity#Logarithmic time|logarithmic time]] in the [[Best, worst and average case|worst case]], making <math>O(\log n)</math> comparisons, where <math>n</math> is the number of elements in the array.{{Efn|The <math>O</math> is [[Big O notation]], and <math>\log</math> is the [[logarithm]]. In Big O notation, the base of the logarithm does not matter since every logarithm of a given base is a constant factor of another logarithm of another base. That is, <math>\log_b(n) = \log_k(n) \div \log_k(b)</math>, where <math>\log_k(b)</math> is a constant.}}<ref name="FloresMadpis1971">{{Cite journal |last=Flores |first=Ivan |last2=Madpis |first2=George |title=Average binary search length for dense ordered lists |journal=[[Communications of the ACM]] |date=1971-09-01 |volume=14 |issue=9 |page=602–603 |doi=10.1145/362663.362752 |issn=0001-0782 |s2cid=43325465 |doi-access=free}}</ref> 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.

== 算法 ==
二分查找适用于有序数组。二分查找首先比较数组中间的元素与目标值。如果目标值与该元素匹配，则返回该元素在数组中的位置；如果目标值小于该元素，则在数组较小的那一半中继续查找；如果目标值大于该元素，则在数组较大的那一半中继续查找。通过这种方法，每次迭代都能将搜索范围缩小一半。{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}

=== 过程 ===
给定一个包含<math>n</math>个元素的数组<math>A</math>，其中的值或[[记录]]分别为<math>A_0,A_1,A_2,\ldots,A_{n-1}</math>，且满足<math>A_0 \leq A_1 \leq A_2 \leq \cdots \leq A_{n-1}</math>。假设目标值为<math>T</math>。下面的[[子程序]]使用二分查找来寻找<math>T</math>在数组<math>A</math>中的索引。{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}
# 取<math>L</math>为<math> 0</math>，<math>R</math>为<math>n-1</math>。
# 如果<math>L>R</math>，则搜索失败并终止。
# 取<math>m</math>（中间元素的位置）为<math>\frac{L+R}{2}</math>的[[向下取整]]值，即不大于<math>\frac{L+R}{2}</math>的最大整数。
# 如果<math>A_m < T</math>，则取<math>L</math>为<math>m+1</math>，并返回步骤2。
# 如果<math>A_m > T</math>，则取<math>R</math>为<math>m-1</math>，并返回步骤2。
# 如果<math>A_m = T</math>，则搜索完成，返回<math>m</math>。

这个迭代过程使用两个变量<math>L</math>和<math>R</math>来跟踪搜索边界。该过程可以用[[伪代码]]表示如下，其中变量名和类型与上文相同，<code>floor</code>为[[下取整函数]]，<code>unsuccessful</code>表示搜索失败时的特定返回值：{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}
[[File:Binary-search-work.gif|thumb|right|二分查找过程]]
 '''function''' binary_search(A, n, T) '''is'''
     L := 0
     R := n &minus; 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 &minus; 1
         '''else''':
             '''return''' m
     '''return''' unsuccessful

也可取<math>m</math>为<math>\frac{L+R}{2}</math>的[[向上取整]]值。如此所做，若目标值在数组中出现多次，结果可能会有所不同。

==== 替代过程 ====
上述过程中，每次迭代都会检查中间元素（<math>m</math>）是否等于目标值（<math>T</math>）。而在其他一些实现中，仅剩下一个元素（即<math>L=R</math>）时，才会执行这项检查，这样每次迭代时就无需检查。这种方式的比较循环更快，因为每次迭代少了一次比较，但平均只需要多一次迭代。<ref name="Bottenbruch1962">{{Cite journal |last=Bottenbruch |first=Hermann |title=Structure and use of ALGOL 60 |journal=[[Journal of the ACM]] |date=1962-04-01 |volume=9 |issue=2 |page=161–221 |doi=10.1145/321119.321120 |issn=0004-5411 |s2cid=13406983 |doi-access=free}} Procedure is described at p. 214 (§43), titled "Program for Binary Search".</ref>

{{Le|赫尔曼·博滕布鲁赫|Hermann Bottenbruch}}于1962年首次发表了省略此检查的实现。<ref name="Bottenbruch1962" />{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}

# 取<math>L</math>为<math> 0</math>，<math>R</math>为<math>n-1</math>。
# 当<math>L \neq R</math>时，
## 取<math>m</math>（中间元素的位置）为<math>\frac{L+R}{2}</math>的[[向上取整]]值，即不小于<math>\frac{L+R}{2}</math>的最小整数。
## 如果<math>A_m > T</math>，取<math>R</math>为<math>m-1</math>。
## 否则说明<math>A_m \leq T</math>，取<math>L</math>为<math>m</math>。
# 现在<math>L=R</math>，搜索完成。如果<math>A_L=T</math>，返回<math>L</math>。否则，搜索失败并终止。

该版本的伪代码如下，其中<code>ceil</code>是上取整函数：

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

=== 重复元素 ===
即使数组中存在重复元素，算法可能返回任意一个与目标值相等的索引。例如，如果要搜索的数组为<math>[1,2,3,4,4,5,6,7]</math>，且目标值为<math>4</math>，那么算法返回第4个（索引为 3）或第5个（索引为4）元素都是正确的。常规过程通常返回第4个元素（索引为3），但并不总是返回第一个重复项（考虑数组<math>[1,2,4,4,4,5,6,7]</math>，这时依然返回第4个元素）。然而，有时需要找到目标值在数组中重复出现的最左侧或最右侧的元素。在上述例子中，第4个元素是值为4的最左侧元素，而第5个元素是值为4的最右侧元素。上述的替代过程总是会返回最右侧元素的索引（如果该元素存在的话）。{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}

==== 查找最左侧元素的过程 ====
要查找最左边的元素，可以使用以下过程：{{Sfn|Kasahara|Morishita|2006|pp=8–9}}

# 取<math>L</math>为<math> 0</math>，<math>R</math>为<math>n</math>。
# 当<math>L < R</math>时，
## 取<math>m</math>（中间元素的位置）为<math>\frac{L+R}{2}</math>的向下取整值，即不大于<math>\frac{L+R}{2}</math>的最大整数。
## 如果<math>A_m < T</math>，取<math>L</math>为<math>m+1</math>。
## 否则说明<math>A_m \geq T</math>，取''<math>R</math>''为<math>m</math>。
# 返回<math>L</math>。

如果<math>L < n</math>且<math>A_L = T</math>，那么<math>A_L</math>是等于<math>T</math>的最左侧元素。即使<math>T</math>不在数组中，<math>L</math>也是<math>T</math>在数组中的[[#近似匹配|排序位置]]，即数组中小于<math>T</math>的元素数量。

该版本的伪代码如下，其中<code>floor</code>是下取整函数：

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

==== 查找最右侧元素的过程 ====
要查找最右边的元素，可以使用以下过程：{{Sfn|Kasahara|Morishita|2006|pp=8–9}}

# 取<math>L</math>为<math> 0</math>，<math>R</math>为<math>n</math>。
# 当<math>L < R</math>时，
## 取<math>m</math>（中间元素的位置）为<math>\frac{L+R}{2}</math>的向下取整值，即不大于<math>\frac{L+R}{2}</math>的最大整数。
## 如果<math>A_m > T</math>，取<math>R</math>为<math>m</math>。
## 否则说明<math>A_m \leq T</math>，取''<math>L</math>''为<math>m+1</math>。
# 返回<math>R - 1</math>。

如果<math>R > 0</math> 且<math>A_{R-1}=T</math>，那么<math>A_{R-1}</math>是等于<math>T</math>的最右侧元素。即使''<math>T</math>''不在数组中，<math>n-R</math>也是数组中大于''<math>T</math>''的元素数量。

该版本的伪代码如下，其中<code>floor</code>是下取整函数：

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

=== 近似匹配 ===
[[File:Approximate-binary-search.svg|thumb|upright=1.5|class=skin-invert-image|二分查找可计算近似匹配。上图中，目标值<math>5</math>本身不在数组中，但通过近似匹配，能计算出其排序位置、前驱、后继、最近邻]]
上述过程仅用于精确匹配，即找到目标值的位置。然而，由于二分查找在有序数组上进行，所以很容易扩展它以执行近似匹配。例如，二分查找可以用来计算给定值的排序位置（即比它小的元素的数量）、前驱（前一个较小的元素）、后继（下一个较大的元素）、[[最近邻搜索|最近邻]]。{{Le|范围查询 (计算机科学)|Range query (computer science)|范围查询}}（查找两个值之间的元素数量）可以通过查询两次排序位置来完成。{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Rank and selection"}}
* 查询排序位置可以使用[[#查找最左侧元素的过程|查找最左侧元素的过程]]来完成。程序的返回值即为小于目标值的元素数量。{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Rank and selection"}}
* 查询前驱可以通过查询排序位置来执行。如果目标值的排序位置为<math>r</math>，那么其前驱的位置为<math>r-1</math>。{{Sfn|Goldman|Goldman|2008|pp=461–463}}
* 对于后继查询，可以[[#查找最右侧元素的过程|查找最右侧元素]]。如果得到的结果为''<math>r</math>''，那么目标值的后继位置就是<math>r+1</math>。{{Sfn|Goldman|Goldman|2008|pp=461–463}}
* 目标值的最近邻是其前驱或后继之一，取决于哪个位置更接近。
* 区间查询也很简单。{{Sfn|Goldman|Goldman|2008|pp=461–463}}一旦知道了两个值的位置，区间内大于等于第一个值且小于第二个值的元素数量就是两个位置之差。考虑到是否需要将区间的端点包含在内，以及数组中是否包含与端点匹配的元素，其结果可能会增加或减少1。{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Range queries"}}

== 性能 ==
{{hatnote|此章节中，<math display="inline">\lfloor\cdot \rfloor</math>表示[[下取整函数|向下取整]]，<math display="inline">\log_2</math>是[[以2为底的对数]]。}}
[[File:Binary search example tree.svg|thumb|upright|class=skin-invert-image|表示二分查找的[[树 (数据结构)|树]]。这里要查找的数组是<math>[20, 30, 40, 50, 80, 90, 100]</math>，目标值是<math>40</math>]]
[[File:Binary search complexity.svg|thumb|upright=1.6|class=skin-invert-image|最坏情况下，搜索到达树的最深层；而最好情况是目标值正好为中间元素]]

就比较次数而言，可以将二分查找的过程放在[[二叉树]]上执行，以分析其性能。树的根节点是数组的中间元素。左半部分的中间元素是根节点的左子节点，右半部分的中间元素是根节点的右子节点，其余部分以类似方式构建。搜索过程从根节点开始，根据目标值是小于还是大于当前节点的值来选择遍历左子树还是右子树。<ref name="FloresMadpis1971" />{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

最坏情况下，二分查找需要比较<math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math>次。此时搜索会达到树的最深层，并且对于任何二分查找，树的层数总为<math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math>。若目标元素不在数组中，可能会发生最坏情况：若<math display="inline">n</math>可以表示为2的某次幂减1，那么查找过程总会遍历到最深层，一定会发生最坏情况；否则，搜索过程可能会在倒数第二层中止，此时比较了<math display="inline">\lfloor \log_2 (n) \rfloor</math>次，比最坏情况少一次。{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), "Theorem B"}}

平均情况下，当目标元素在数组中时，二分查找的比较次数是<math>\lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n</math>（假设每个元素被搜索的概率相等），近似于<math>\log_2(n) - 1</math>；若目标元素不在数组中，二分查找的比较次数平均为<math>\lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)</math>（假设范围内及范围外的元素被搜索的概率相等）。{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

最好情况下，即目标值正好是数组的中间元素，二分查找在一次比较后就能返回其位置。{{Sfn|Chang|2003|p=169}}

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.{{Efn|Any search algorithm based solely on comparisons can be represented using a binary comparison tree. An ''internal path'' is any path from the root to an existing node. Let <math>I</math> be the ''internal path length'', the sum of the lengths of all internal paths. If each element is equally likely to be searched, the average case is <math>1 + \frac{I}{n}</math> or simply one plus the average of all the internal path lengths of the tree. This is because internal paths represent the elements that the search algorithm compares to the target. The lengths of these internal paths represent the number of iterations ''after'' the root node. Adding the average of these lengths to the one iteration at the root yields the average case. Therefore, to minimize the average number of comparisons, the internal path length <math>I</math> must be minimized. It turns out that the tree for binary search minimizes the internal path length. {{Harvnb|Knuth|1998}} proved that the ''external path'' length (the path length over all nodes where both children are present for each already-existing node) is minimized when the external nodes (the nodes with no children) lie within two consecutive levels of the tree. This also applies to internal paths as internal path length <math>I</math> is linearly related to external path length <math>E</math>. For any tree of <math>n</math> nodes, <math>I = E - 2n</math>. When each subtree has a similar number of nodes, or equivalently the array is divided into halves in each iteration, the external nodes as well as their interior parent nodes lie within two levels. It follows that binary search minimizes the number of average comparisons as its comparison tree has the lowest possible internal path length.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}}} 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.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

=== 空间复杂度 ===
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 <math>O(1)</math> 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 [[Interval (mathematics)|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 <math>n</math>, 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 <math>n + 1</math> intervals.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

==== 成功的搜索 ====
<!-- E stands for "expected" -->
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 <math>l</math>, is <math>l + 1</math> 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 <math>n</math> elements, which is a positive integer, and the internal path length is <math>I(n)</math>, then the average number of iterations for a successful search <math>T(n) = 1 + \frac{I(n)}{n}</math>, with the one iteration added to count the initial iteration.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

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 <math>n</math> nodes, which is equal to:{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}}

<math>
I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor
</math>

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:{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}}

<math>
\sum_{k=1}^7 \left \lfloor \log_2(k) \right \rfloor = 0 + 2(1) + 4(2) = 2 + 8 = 10
</math>

The average number of iterations would be <math>1 + \frac{10}{7} = 2 \frac{3}{7}</math> based on the equation for the average case. The sum for <math>I(n)</math> can be simplified to:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
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
</math>

Substituting the equation for <math>I(n)</math> into the equation for <math>T(n)</math>:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
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
</math>

For integer <math>n</math>, 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 <math>n</math> elements, which is a positive integer, and the external path length is <math>E(n)</math>, then the average number of iterations for an unsuccessful search <math>T'(n)=\frac{E(n)}{n+1}</math>, with the one iteration added to count the initial iteration. The external path length is divided by <math>n+1</math> instead of <math>n</math> because there are <math>n+1</math> external paths, representing the intervals between and outside the elements of the array.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

This problem can similarly be reduced to determining the minimum external path length of all binary trees with <math>n</math> nodes. For all binary trees, the external path length is equal to the internal path length plus <math>2n</math>.{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}} Substituting the equation for <math>I(n)</math>:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
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}
</math>

Substituting the equation for <math>E(n)</math> into the equation for <math>T'(n)</math>, the average case for unsuccessful searches can be determined:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
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)
</math>

==== 另一过程的性能 ====
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 <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> times in the worst case, the slight increase in efficiency per iteration does not compensate for the extra iteration for all but very large <math display="inline">n</math>.{{Efn|{{Harvnb|Knuth|1998}} showed on his [[MIX (abstract machine)|MIX]] computer model, which Knuth designed as a representation of an ordinary computer, that the average running time of this variation for a successful search is <math display="inline">17.5 \log_2 n + 17</math> units of time compared to <math display="inline">18 \log_2 n - 16</math> units for regular binary search. The time complexity for this variation grows slightly more slowly, but at the cost of higher initial complexity. {{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 23"}}}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 23"}}<ref>{{Cite journal |last=Rolfe |first=Timothy J. |title=Analytic derivation of comparisons in binary search |journal=ACM SIGNUM Newsletter |date=1997 |volume=32 |issue=4 |page=15–19 |doi=10.1145/289251.289255 |s2cid=23752485 |doi-access=free}}</ref>

=== 运行时间和缓存使用 ===
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 [[bit]]s) 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 arithmetic|floating-point]] values (the most common digital representation of [[real number]]s) is often more expensive than comparing integers or short strings.<ref name="KhuongMorin2017">{{Cite journal |last=Khuong |first=Paul-Virak |last2=Morin |first2=Pat |author-link2=Pat Morin |title=Array Layouts for Comparison-Based Searching |journal=Journal of Experimental Algorithmics |year=2017 |volume=22 |at=Article 1.3 |arxiv=1509.05053 |doi=10.1145/3053370 |s2cid=23752485}}</ref>

On most computer architectures, the [[Central processing unit|processor]] has a hardware [[Cache (computing)|cache]] separate from [[Random-access memory|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.<ref name="KhuongMorin2017" />

== 二分搜索与其他方案 ==
Sorted arrays with binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval, taking <math display="inline">O(n)</math> time for each such operation. In addition, sorted arrays can complicate memory use especially when elements are often inserted into the array.{{Sfn|Knuth|1997|loc=§2.2.2 ("Sequential Allocation")}} There are other data structures that support much more efficient insertion and deletion. Binary search can be used to perform exact matching and [[Set (abstract data type)|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 <math display="inline">O(\log n)</math> time regardless of the type or structure of the values themselves.<ref name="pred">{{Cite journal |last=Beame |first=Paul |last2=Fich |first2=Faith E. |author-link2=Faith Ellen |title=Optimal bounds for the predecessor problem and related problems |journal=[[Journal of Computer and System Sciences]] |date=2001 |volume=65 |issue=1 |page=38–72 |doi=10.1006/jcss.2002.1822 |doi-access=free}}</ref> In addition, there are some operations, like finding the smallest and largest element, that can be performed efficiently on a sorted array.{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Rank and selection"}}

=== 线性搜索 ===
[[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|{{Harvnb|Knuth|1998}} performed a formal time performance analysis of both of these search algorithms. On Knuth's [[MIX (abstract machine)|MIX]] computer, which Knuth designed as a representation of an ordinary computer, binary search takes on average <math display="inline">18 \log n - 16</math> units of time for a successful search, while linear search with a [[sentinel node]] at the end of the list takes <math display="inline">1.75n + 8.5 - \frac{n \text{ mod } 2}{4n}</math> 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 <math display="inline">n > 44</math>.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}{{Sfn|Knuth|1998|loc=Answers to Exercises  (§6.2.1) for "Exercise 5"}}}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table")}} All [[sorting algorithm]]s based on comparing elements, such as [[quicksort]] and [[merge sort]], require at least <math display="inline">O(n \log n)</math> comparisons in the worst case.{{Sfn|Knuth|1998|loc=§5.3.1 ("Minimum-Comparison sorting")}} 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.{{Sfn|Sedgewick|Wayne|2011|loc=§3.2 ("Ordered symbol tables")}}

=== 二叉树 ===
[[File:Binary search tree search 4.svg|thumb|right|class=skin-invert-image|[[Binary search tree]]s 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.<ref name="pred" />{{Sfn|Sedgewick|Wayne|2011|loc=§3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion"}}

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 [[self-balancing binary search tree|balanced binary search tree]]s, 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 <math display="inline">n</math> comparisons.{{Efn|Inserting the values in sorted order or in an alternating lowest-highest key pattern will result in a binary search tree that maximizes the average and worst-case search time.{{Sfn|Knuth|1998|loc=§6.2.2 ("Binary tree searching"), subsection "But what about the worst case?"}}}} Binary search trees take more space than sorted arrays.{{Sfn|Sedgewick|Wayne|2011|loc=§3.5 ("Applications"), "Which symbol-table implementation should I use?"}}

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 [[database]]s and [[filesystem]]s.{{Sfn|Knuth|1998|loc=§5.4.9 ("Disks and Drums")}}{{Sfn|Knuth|1998|loc=§6.2.4 ("Multiway trees")}}

=== 散列表 ===
For implementing [[associative arrays]], [[hash table]]s, a data structure that maps keys to [[record (computer science)|records]] using a [[hash function]], are generally faster than binary search on a sorted array of records.{{Sfn|Knuth|1998|loc=§6.4 ("Hashing")}} Most hash table implementations require only [[Amortized analysis|amortized]] constant time on average.{{efn|It is possible to search some hash table implementations in guaranteed constant time.{{Sfn|Knuth|1998|loc=§6.4 ("Hashing"), subsection "History"}}}}<ref>{{Cite journal |last=Dietzfelbinger |first=Martin |last2=Karlin |first2=Anna |author-link2=Anna Karlin |last3=Mehlhorn |first3=Kurt |author-link3=Kurt Mehlhorn |last4=Meyer auf der Heide |first4=Friedhelm |last5=Rohnert |first5=Hans |last6=Tarjan |first6=Robert E. |author-link6=Robert Tarjan |title=Dynamic perfect hashing: upper and lower bounds |journal=[[SIAM Journal on Computing]] |date=August 1994 |volume=23 |issue=4 |page=738–761 |doi=10.1137/S0097539791194094}}</ref> 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.<ref>{{Cite web |title=Hash tables |url=http://cglab.ca/~morin/teaching/5408/notes/hashing.pdf |last=Morin |first=Pat |url-status=live |archive-url=https://ghostarchive.org/archive/20221009/http://cglab.ca/~morin/teaching/5408/notes/hashing.pdf |archive-date=2022-10-09 |access-date=2016-03-28 |page=1}}</ref> 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.<ref name="pred" />

=== 集合 ===
A related problem to search is [[Set (abstract data type)|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 [[bit]]s, with each bit representing a single key within the range of keys. Bit arrays are very fast, requiring only <math display="inline">O(1)</math> time.{{Sfn|Knuth|2011|loc=§7.1.3 ("Bitwise Tricks and Techniques")}}  The Judy1 type of [[Judy array]] handles 64-bit keys efficiently.<ref name="judyarray">{{Citation |last=Silverstein |title=Judy IV shop manual |url=http://judy.sourceforge.net/doc/shop_interm.pdf |first1=Alan |pages=80–81 |publisher=[[Hewlett-Packard]] |archive-url=https://ghostarchive.org/archive/20221009/http://judy.sourceforge.net/doc/shop_interm.pdf |archive-date=2022-10-09 |url-status=live}}</ref>

For approximate results, [[Bloom filter]]s, another probabilistic data structure based on hashing, store a [[set (mathematics)|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 <math display="inline">k</math> hash functions, membership queries require only <math display="inline">O(k)</math> time. However, Bloom filters suffer from [[False positives and false negatives|false positives]].{{Efn|This is because simply setting all of the bits which the hash functions point to for a specific key can affect queries for other keys which have a common hash location for one or more of the functions.<ref name="cuckoofilter">{{Cite conference |last=Fan |first=Bin |last2=Andersen |first2=Dave G. |last3=Kaminsky |first3=Michael |last4=Mitzenmacher |first4=Michael D. |date=2014 |title=Cuckoo filter: practically better than Bloom |conference=Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies |pages=75–88 |doi=10.1145/2674005.2674994 |doi-access=free}}</ref>}}{{Efn|There exist improvements of the Bloom filter which improve on its complexity or support deletion; for example, the cuckoo filter exploits [[cuckoo hashing]] to gain these advantages.<ref name="cuckoofilter" />}}<ref>{{Cite journal |last=Bloom |first=Burton H. |title=Space/time trade-offs in hash coding with allowable errors |journal=[[Communications of the ACM]] |date=1970 |volume=13 |issue=7 |page=422–426 |citeseerx=10.1.1.641.9096 |doi=10.1145/362686.362692 |s2cid=7931252}}</ref>

=== 其他数据结构 ===
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 tree]]s, [[fusion tree]]s, [[trie]]s, and [[bit array]]s. 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.<ref name="pred" /> 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.<ref name="judyarray" />

== 其他形式 ==

=== 统一二分查找 ===
{{Main|Uniform binary search}}
[[File:Uniform binary search.svg|thumb|upright=1.0|class=skin-invert-image|[[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 {{math|[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]}}, the middle element (<math>m</math>) would be {{math|6}}. In this case, the middle element of the left subarray ({{math|[1, 2, 3, 4, 5]}}) is {{math|3}} and the middle element of the right subarray ({{math|[7, 8, 9, 10, 11]}}) is {{math|9}}. Uniform binary search would store the value of {{math|3}} as both indices differ from {{math|6}} by this same amount.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "An important variation"}} 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 computer]]s.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm U"}}

=== 指数搜索{{anchor|One-sided search}} ===
{{Main|Exponential search}}
[[File:Exponential search.svg|thumb|upright=1.5|class=skin-invert-image|Visualization of [[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 <math display="inline">\lfloor \log_2 x + 1\rfloor</math> iterations before binary search is started and at most <math display="inline">\lfloor \log_2 x \rfloor</math> iterations of the binary search, where <math display="inline">x</math> 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.{{sfn|Moffat|Turpin|2002|p=33}}

=== 插值搜索 ===
{{Main|插值搜索}}
[[File:Interpolation search.svg|thumb|upright=1.5|class=skin-invert-image|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.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Interpolation search"}}

A common interpolation function is [[linear interpolation]]. If <math>A</math> is the array, <math>L, R</math> are the lower and upper bounds respectively, and <math>T</math> is the target, then the target is estimated to be about <math>(T - A_L) / (A_R - A_L)</math> of the way between <math>L</math> and <math>R</math>. When linear interpolation is used, and the distribution of the array elements is uniform or near uniform, interpolation search makes <math display="inline">O(\log \log n)</math> comparisons.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Interpolation search"}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 22"}}<ref>{{Cite journal |last=Perl |first=Yehoshua |last2=Itai |first2=Alon |last3=Avni |first3=Haim |title=Interpolation search—a log log ''n'' search |journal=[[Communications of the ACM]] |date=1978 |volume=21 |issue=7 |page=550–553 |doi=10.1145/359545.359557 |s2cid=11089655 |doi-access=free}}</ref>

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.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Interpolation search"}}

=== 分数级联 ===
{{Main|Fractional cascading}}
[[File:Fractional cascading.svg|thumb|upright=1.8|class=skin-invert-image|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 <math display="inline">O(k \log n)</math> time, where <math display="inline">k</math> is the number of arrays. Fractional cascading reduces this to <math display="inline">O(k + \log n)</math> by storing specific information in each array about each element and its position in the other arrays.<ref name="ChazelleLiu2001">{{Cite conference |last=Chazelle |first=Bernard |author-link=Bernard Chazelle |last2=Liu |first2=Ding |date=2001-07-06 |title=Lower bounds for intersection searching and fractional cascading in higher dimension |url=https://dl.acm.org/citation.cfm?doid=380752.380818 |conference=33rd [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]] |publisher=ACM |pages=322–329 |doi=10.1145/380752.380818 |isbn=978-1-58113-349-3 |access-date=2018-06-30}}</ref><ref name="ChazelleLiu2004">{{Cite journal |last=Chazelle |first=Bernard |author-link=Bernard Chazelle |last2=Liu |first2=Ding |title=Lower bounds for intersection searching and fractional cascading in higher dimension |url=http://www.cs.princeton.edu/~chazelle/pubs/FClowerbounds.pdf |url-status=live |journal=Journal of Computer and System Sciences |language=en |date=2004-03-01 |volume=68 |issue=2 |page=269–284 |citeseerx=10.1.1.298.7772 |doi=10.1016/j.jcss.2003.07.003 |issn=0022-0000 |archive-url=https://ghostarchive.org/archive/20221009/http://www.cs.princeton.edu/~chazelle/pubs/FClowerbounds.pdf |archive-date=2022-10-09 |access-date=2018-06-30}}</ref>

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.<ref name="ChazelleLiu2001" />

=== 推广到图表 ===
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&mdash;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 <math>O(\log n)</math> queries in the worst case.<ref>{{Cite conference |last=Emamjomeh-Zadeh |first=Ehsan |last2=Kempe |first2=David |last3=Singhal |first3=Vikrant |date=2016 |title=Deterministic and probabilistic binary search in graphs |conference=48th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]] |pages=519–532 |arxiv=1503.00805 |doi=10.1145/2897518.2897656}}</ref>

=== 嘈杂二分查找 ===
[[File:Noisy binary search.svg|thumb|right|class=skin-invert-image|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 <math>(1 - \tau)\frac{\log_2 (n)}{H(p)} - \frac{10}{H(p)}</math> comparisons on average, where <math>H(p) = -p \log_2 (p) - (1 - p) \log_2 (1 - p)</math><!-- Attribution of LaTeX code: see history of https://en.wikipedia.org/wiki/Binary_entropy_function --> is the [[binary entropy function]] and <math>\tau</math> is the probability that the procedure yields the wrong position.<ref>{{Cite conference |last=Ben-Or |first=Michael |last2=Hassidim |first2=Avinatan |date=2008 |title=The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well) |url=http://www2.lns.mit.edu/~avinatan/research/search-full.pdf |pages=221–230 |doi=10.1109/FOCS.2008.58 |isbn=978-0-7695-3436-7 |archive-url=https://ghostarchive.org/archive/20221009/http://www2.lns.mit.edu/~avinatan/research/search-full.pdf |archive-date=2022-10-09 |book-title=49th [[Annual IEEE Symposium on Foundations of Computer Science|Symposium on Foundations of Computer Science]] |url-status=live}}</ref><ref name="pelc1989">{{Cite journal |last=Pelc |first=Andrzej |title=Searching with known error probability |journal=Theoretical Computer Science |date=1989 |volume=63 |issue=2 |page=185–202 |doi=10.1016/0304-3975(89)90077-7 |doi-access=free}}</ref><ref>{{Cite conference |last=Rivest |first=Ronald L. |author-link=Ronald Rivest |last2=Meyer |first2=Albert R. |author-link2=Albert R. Meyer |last3=Kleitman |first3=Daniel J. |author-link3=Daniel Kleitman |last4=Winklmann |first4=K. |title=Coping with errors in binary search procedures |conference=10th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]] |doi=10.1145/800133.804351 |doi-access=free}}</ref> The noisy binary search problem can be considered as a case of the [[Ulam's game|Rényi-Ulam game]],<ref>{{Cite journal |last=Pelc |first=Andrzej |title=Searching games with errors—fifty years of coping with liars |journal=Theoretical Computer Science |date=2002 |volume=270 |issue=1–2 |page=71–109 |doi=10.1016/S0304-3975(01)00303-6 |doi-access=free}}</ref> a variant of [[Twenty Questions]] where the answers may be wrong.<ref>{{Cite journal |last=Rényi |first=Alfréd |title=On a problem in information theory |journal=Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei |language=hu |year=1961 |volume=6 |page=505–516 |mr=0143666}}</ref>

=== 量子二分查找 ===
Classical computers are bounded to the worst case of exactly <math display="inline">\lfloor \log_2 n + 1 \rfloor</math> iterations when performing binary search. [[Quantum algorithm]]s for binary search are still bounded to a proportion of <math display="inline">\log_2 n</math> queries (representing iterations of the classical procedure), but the constant factor is less than one, providing for a lower time complexity on [[quantum computing|quantum computers]]. Any ''exact'' quantum binary search procedure—that is, a procedure that always yields the correct result—requires at least <math display="inline">\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n</math> queries in the worst case, where <math display="inline">\ln</math> is the [[natural logarithm]].<ref>{{Cite journal |last=Høyer |first=Peter |last2=Neerbek |first2=Jan |last3=Shi |first3=Yaoyun |title=Quantum complexities of ordered searching, sorting, and element distinctness |journal=[[Algorithmica]] |date=2002 |volume=34 |issue=4 |page=429–448 |arxiv=quant-ph/0102078 |doi=10.1007/s00453-002-0976-3 |s2cid=13717616}}</ref> There is an exact quantum binary search procedure that runs in <math display="inline">4 \log_{605} n \approx 0.433 \log_2 n</math> queries in the worst case.<ref name="quantumalgo">{{Cite journal |last=Childs |first=Andrew M. |last2=Landahl |first2=Andrew J. |last3=Parrilo |first3=Pablo A. |title=Quantum algorithms for the ordered search problem via semidefinite programming |journal=Physical Review A |date=2007 |volume=75 |issue=3 |at=032335 |arxiv=quant-ph/0608161 |bibcode=2007PhRvA..75c2335C |doi=10.1103/PhysRevA.75.032335 |s2cid=41539957}}</ref> In comparison, [[Grover's algorithm]] is the optimal quantum algorithm for searching an unordered list of elements, and it requires <math>O(\sqrt{n})</math> queries.<ref>{{Cite conference |last=Grover |first=Lov K. |author-link=Lov Grover |date=1996 |title=A fast quantum mechanical algorithm for database search |conference=28th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]] |location=Philadelphia, PA |pages=212–219 |arxiv=quant-ph/9605043 |doi=10.1145/237814.237866}}</ref>

== 历史 ==
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 {{circa|200 BCE}}. The tablet contained about 500 [[sexagesimal]] numbers and their [[Multiplicative inverse|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 (1286)|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.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}

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.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}} In 1957, [[W. Wesley Peterson|William Wesley Peterson]] published the first method for interpolation search.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}}<ref>{{Cite journal |last=Peterson |first=William Wesley |author-link=W. Wesley Peterson |title=Addressing for random-access storage |journal=IBM Journal of Research and Development |date=1957 |volume=1 |issue=2 |page=130–146 |doi=10.1147/rd.12.0130}}</ref> Every published binary search algorithm worked only for arrays whose length is one less than a power of two{{efn|That is, arrays of length 1, 3, 7, 15, 31 ...<ref>"2<sup>''n''</sup>&minus;1". [[On-Line Encyclopedia of Integer Sequences|OEIS]] [http://oeis.org/A000225 A000225] {{Webarchive|url=https://web.archive.org/web/20160608084228/http://oeis.org/A000225 |date=2016-06-08 }}.  Retrieved 7 May 2016.</ref>}} until 1960, when [[Derrick Henry Lehmer]] published a binary search algorithm that worked on all arrays.<ref>{{Cite journal |author=Lehmer, Derrick |title=Teaching combinatorial tricks to a computer |journal=Proceedings of Symposia in Applied Mathematics |year=1960 |volume=10 |page=180–181 |doi=10.1090/psapm/010 |isbn=9780821813102 |doi-access=free}}</ref> In 1962, Hermann Bottenbruch presented an [[ALGOL 60]] implementation of binary search that placed the [[#Alternative procedure|comparison for equality at the end]], increasing the average number of iterations by one, but reducing to one the number of comparisons per iteration.<ref name="Bottenbruch1962" /> The [[#Uniform binary search|uniform binary search]] was developed by A. K. Chandra of [[Stanford University]] in 1971.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}} In 1986, [[Bernard Chazelle]] and [[Leonidas J. Guibas]] introduced [[fractional cascading]] as a method to solve numerous search problems in [[computational geometry]].<ref name="ChazelleLiu2001" /><ref>{{Cite journal |last=Chazelle |first=Bernard |author-link=Bernard Chazelle |last2=Guibas |first2=Leonidas J. |author-link2=Leonidas J. Guibas |title=Fractional cascading: I. A data structuring technique |url=http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading1.pdf |journal=[[Algorithmica]] |year=1986 |volume=1 |issue=1–4 |page=133–162 |citeseerx=10.1.1.117.8349 |doi=10.1007/BF01840440 |s2cid=12745042}}</ref><ref>{{Citation |last=Chazelle |title=Fractional cascading: II. Applications |url=http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading2.pdf |year=1986 |last2=Guibas |first1=Bernard |first2=Leonidas J. |journal=[[Algorithmica]] |volume=1 |issue=1–4 |pages=163–191 |doi=10.1007/BF01840441 |author-link1=Bernard Chazelle |s2cid=11232235 |author-link2=Leonidas J. Guibas}}</ref>

== 实现问题 ==
{{Blockquote|尽管二分查找的基本思想相对简单，但其细节却出奇复杂。|[[高德纳]]{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}} }}

[[喬恩·本特利 (計算機科學家)|乔恩·本特利]]在为职业程序员开设的一门课程中布置了二分查找的练习，发现90%的学生在数小时后仍未能给出正确的解答。主要原因是算法实现有误而无法运行，或是在极少数{{Le|边界情况|Edge case}}下返回错误答案。{{Sfn|Bentley|2000|loc=§4.1 ("The Challenge of Binary Search")}}1988年发表的一项研究显示，二十本教材中只有五本给出了准确的二分查找代码。<ref name="textbook">{{Cite journal |last=Pattis |first=Richard E. |author-link=Richard E. Pattis |title=Textbook errors in binary searching |journal=SIGCSE Bulletin |year=1988 |volume=20 |page=190–194 |doi=10.1145/52965.53012}}</ref>此外，本特利自身在1986年出版的《编程珠玑》一书中给出的二分查找实现存在[[整数溢出|溢出错误]]，这个错误在二十多年里未被发现。[[Java|Java编程语言]]库中的二分查找实现也存在相同的溢出问题，且该问题持续了九年多。<ref>{{Cite web |title=Extra, extra – read all about it: nearly all binary searches and mergesorts are broken |url=http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html |website=Google Research Blog |date=2006-06-02 |author-link=Joshua Bloch |last=Bloch |first=Joshua |url-status=live |archive-url=https://web.archive.org/web/20160401140544/http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html |archive-date=2016-04-01 |access-date=2016-04-21}}</ref>

在实际编程中，表示索引的变量通常是固定大小的（整数）。因此在处理非常大的数组时，可能会导致[[算术溢出]]。如果使用<math>\frac{L+R}{2}</math>计算中点，即使<math>L</math>和<math>R</math>的值都在所用[[数据类型]]的表示范围内，<math>L+R</math>的值仍可能会超过范围。如果''<math>L</math>''和<math>R</math>都是非负数，可以通过计算<math>L+\frac{R-L}{2}</math>来避免这种情况。<ref name="semisum">{{Cite journal |last=Ruggieri |first=Salvatore |title=On computing the semi-sum of two integers |url=http://www.di.unipi.it/~ruggieri/Papers/semisum.pdf |url-status=live |journal=[[Information Processing Letters]] |date=2003 |volume=87 |issue=2 |page=67–71 |citeseerx=10.1.1.13.5631 |doi=10.1016/S0020-0190(03)00263-1 |archive-url=https://web.archive.org/web/20060703173514/http://www.di.unipi.it/~ruggieri/Papers/semisum.pdf |archive-date=2006-07-03 |access-date=2016-03-19}}</ref>

如果循环的退出条件定义不正确，可能会导致无限循环。当''<math>L</math>''超过<math>R</math>时，表示搜索失败，必须返回失败的信息。另外，循环应在找到目标元素时退出；若不这么做，那么在循环结束后，必须检查是否成功找到目标元素。本特利发现，大多数在实现二分查找时出错的程序员，都是在定义退出条件时犯了错。<ref name="Bottenbruch1962" />{{Sfn|Bentley|2000|loc=§4.4 ("Principles")}}

== 库支持 ==
许多编程语言的[[标准库]]包含二分查找例程：

* [[C语言]]在其[[C標準函式庫|标准库]]中提供了<code>bsearch()</code>[[子程序|函数]]，通常使用二分查找实现，尽管官方标准中并未强制要求。<ref>{{Cite web |title=bsearch – binary search a sorted table |url=http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html |website=The Open Group Base Specifications |date=2013 |url-status=live |archive-url=https://web.archive.org/web/20160321211605/http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html |archive-date=2016-03-21 |access-date=2016-03-28 |publisher=[[The Open Group]] |edition=7th}}</ref>
* [[C++]]的[[C++標準函式庫|标准库]]中提供了<code>binary_search()</code>、<code>lower_bound()</code>、<code>upper_bound()</code>、<code>equal_range()</code>函数。{{Sfn|Stroustrup|2013|p=945}}
* [[D语言]]的标准库Phobos在<code>std.range</code>模块中提供了<code>SortedRange</code>类型（由<code>sort()</code>和<code>assumeSorted()</code>函数返回），该类型包含<code>contains()</code>、<code>equaleRange()</code>、<code>lowerBound()</code>、<code>trisect()</code>方法，这些方法默认对提供随机访问的范围使用二分查找技术。<ref>{{Cite web |title=std.range - D Programming Language |url=https://dlang.org/phobos/std_range.html#SortedRange |website=dlang.org |access-date=2020-04-29}}</ref>
* COBOL提供了<code>SEARCH ALL</code>动词，用于对COBOL有序表执行二分查找。<ref>{{Citation |title=COBOL ANSI-85 programming reference manual |date=2012 |author=Unisys |author-link=Unisys |volume=1 |pages=598–601}}</ref>
* [[Go]]的<code>sort</code>标准库包包含<code>Search</code>、<code>SearchInts</code>、<code>SearchFloat64s</code>、<code>SearchStrings</code>函数，分别实现了通用的二分查找，以及针对整数、浮点数、字符串切片的特定实现。<ref>{{Cite web |title=Package sort |url=http://golang.org/pkg/sort/ |website=The Go Programming Language |url-status=live |archive-url=https://web.archive.org/web/20160425055919/https://golang.org/pkg/sort/ |archive-date=2016-04-25 |access-date=2016-04-28}}</ref>
* Java在标准<code>java.util</code>包的{{Javadoc:SE|java/util|Arrays}}和{{Javadoc:SE|java/util|Collections}}类中提供了一组[[函数重载|重载]]的<code>binarySearch()</code>静态方法，用于对Java数组和<code>List</code>（列表）执行二分查找。<ref>{{Cite web |title=java.util.Arrays |url=https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html |website=Java Platform Standard Edition 8 Documentation |url-status=live |archive-url=https://web.archive.org/web/20160429064301/http://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html |archive-date=2016-04-29 |access-date=2016-05-01 |publisher=[[Oracle Corporation]]}}</ref><ref>{{Cite web |title=java.util.Collections |url=https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html |website=Java Platform Standard Edition 8 Documentation |url-status=live |archive-url=https://web.archive.org/web/20160423092424/https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html |archive-date=2016-04-23 |access-date=2016-05-01 |publisher=[[Oracle Corporation]]}}</ref>
* [[Microsoft]]的[[.NET Framework]] 2.0在其集合基类中提供了二分查找算法的静态[[泛型编程|泛型]]版本，例如<code>System.Array</code>的<code>BinarySearch<T>(T[] array, T value)</code>方法。<ref>{{Cite web |title=List<T>.BinarySearch method (T) |url=https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx |website=Microsoft Developer Network |url-status=live |archive-url=https://web.archive.org/web/20160507141014/https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx |archive-date=2016-05-07 |access-date=2016-04-10}}</ref>
* 对于[[Objective-C]]，[[Cocoa|Cocoa框架]]在[[Mac OS X Snow Leopard|Mac OS X 10.6]]及以上版本中提供了<code>[https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/NSArray.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator: NSArray -indexOfObject:inSortedRange:options:usingComparator:]</code>方法；<ref>{{Cite web |title=NSArray |url=https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/index.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator: |website=Mac Developer Library |url-status=live |archive-url=https://web.archive.org/web/20160417163718/https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/index.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator: |archive-date=2016-04-17 |access-date=2016-05-01 |publisher=[[Apple Inc.]]}}</ref>苹果的{{Le|Core Foundation}} C框架也包含<code>[https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/Reference/reference.html#//apple_ref/c/func/CFArrayBSearchValues CFArrayBSearchValues()]</code>函数。<ref>{{Cite web |title=CFArray |url=https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/index.html#//apple_ref/c/func/CFArrayBSearchValues |website=Mac Developer Library |url-status=live |archive-url=https://web.archive.org/web/20160420193823/https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/index.html#//apple_ref/c/func/CFArrayBSearchValues |archive-date=2016-04-20 |access-date=2016-05-01 |publisher=[[Apple Inc.]]}}</ref>
* [[Python]]提供了模块<code>bisect</code>，在插入元素后仍能保持列表的有序状态，而无需每次插入元素后都对列表排序。<ref>{{Cite web |title=8.6. bisect — Array bisection algorithm |url=https://docs.python.org/3.6/library/bisect.html#module-bisect |website=The Python Standard Library |url-status=live |archive-url=https://web.archive.org/web/20180325105932/https://docs.python.org/3.6/library/bisect.html#module-bisect |archive-date=2018-03-25 |access-date=2018-03-26 |publisher=Python Software Foundation}}</ref>
* [[Ruby]]的Array类包含一个带有内置近似匹配的<code>bsearch</code>方法。{{Sfn|Fitzgerald|2015|p=152}}
* [[Rust]]的切片原始类型提供了<code>binary_search()</code>、<code>binary_search_by()</code>、<code>binary_search_by_key()</code>、<code>partition_point()</code>方法。<ref>{{Cite web |title=Primitive Type <code>slice</code> |url=https://doc.rust-lang.org/std/primitive.slice.html |website=The Rust Standard Library |date=2024 |access-date=2024-05-25 |publisher=[[The Rust Foundation]]}}</ref>

== 参见 ==
* {{annotated link|Bisection method}} – the same idea used to solve equations in the real numbers
* {{annotated link|Multiplicative binary search}}

== 注释和参考文献 ==
<!-- Referencing conventions for this article: use CS1 templates, add book and monograph sources to the Sources section and then cite them using Harvard citations, directly cite other sources. Source titles are in sentence case, but the first letter of proper nouns (e.g., "Bayesian") is capitalized. -->

=== 注释 ===
{{Notelist|30em}}

=== 引用 ===
{{Reflist|30em}}

=== 来源 ===
{{columns-list|colwidth=30em|style=font-size:90%;|
<!-- * {{Cite book |title=The D Programming Language |last=Alexandrescu |first=Andrei |year=2010 |publisher=Addison-Wesley Professional |isbn=0-321-63536-1 |location=Upper Saddle River, New Jersey |language=en |ref=harv}}-->
* {{Cite book |title=Programming pearls |last=Bentley |first=Jon |publisher=[[Addison-Wesley]] |year=2000 |isbn=978-0-201-65788-3 |edition=2nd |language=en |ref=harv |author-link=Jon Bentley (computer scientist)}}
* {{Cite book |title=A dictionary of computer science |last=Butterfield |first=Andrew |last2=Ngondi |first2=Gerard E. |year=2016 |publisher=[[Oxford University Press]] |isbn=978-0-19-968897-5 |edition=7th |location=Oxford, UK |language=en |ref=harv}}
* {{Cite book |title=Data structures and algorithms |last=Chang |first=Shi-Kuo |publisher=[[World Scientific]] |year=2003 |isbn=978-981-238-348-8 |series=Software Engineering and Knowledge Engineering |volume=13 |location=Singapore |language=en |ref=harv}}
* {{Cite book |title=Introduction to algorithms |last=Cormen |first=Thomas H. |last2=Leiserson |first2=Charles E. |last3=Rivest |first3=Ronald L. |authorlink3=Ron Rivest |last4=Stein |first4=Clifford |authorlink4=Clifford Stein |publisher=MIT Press and McGraw-Hill |year=2009 |isbn=978-0-262-03384-8 |edition=3rd |language=en |ref=harv |author1-link=Thomas H. Cormen |author2-link=Charles E. Leiserson |title-link=Introduction to Algorithms}}
* {{Cite book |title=Ruby pocket reference |last=Fitzgerald |first=Michael |year=2015 |publisher=[[O'Reilly Media]] |isbn=978-1-4919-2601-7 |location=Sebastopol, California |language=en |ref=harv}}
* {{Cite book |title=A practical guide to data structures and algorithms using Java |last=Goldman |first=Sally A. |last2=Goldman |first2=Kenneth J. |year=2008 |publisher=[[CRC Press]] |isbn=978-1-58488-455-2 |location=Boca Raton, Florida |language=en |ref=harv |author1-link=Sally Goldman}}
* {{Cite book |title=Large-scale genome sequence processing |last=Kasahara |first=Masahiro |last2=Morishita |first2=Shinichi |year=2006 |publisher=Imperial College Press |isbn=978-1-86094-635-6 |location=London, UK |language=en |ref=harv}}
* {{Cite book |title=Fundamental algorithms |last=Knuth |first=Donald |publisher=Addison-Wesley Professional |year=1997 |isbn=978-0-201-89683-1 |edition=3rd |series=[[The Art of Computer Programming]] |volume=1 |location=Reading, MA |language=en |ref=harv |author-link=Donald Knuth}}
* {{Cite book |title=Sorting and searching |last=Knuth |first=Donald |publisher=Addison-Wesley Professional |year=1998 |isbn=978-0-201-89685-5 |edition=2nd |series=[[The Art of Computer Programming]] |volume=3 |location=Reading, MA |language=en |ref=harv |author-link=Donald Knuth}}
* {{Cite book |title=Combinatorial algorithms |last=Knuth |first=Donald |publisher=Addison-Wesley Professional |year=2011 |isbn=978-0-201-03804-0 |edition=1st |series=[[The Art of Computer Programming]] |volume=4A |location=Reading, MA |language=en |ref=harv |author-link=Donald Knuth}}
<!-- * {{Cite book |title=A Programmer's Companion to Algorithm Analysis |last=Leiss |first=Ernst |year=2007 |publisher=CRC Press |isbn=1-58488-673-0 |location=Boca Raton, Florida |language=en |ref=harv}} -->
* {{Cite book |title=Compression and coding algorithms |last=Moffat |first=Alistair |last2=Turpin |first2=Andrew |year=2002 |publisher=Kluwer Academic Publishers |isbn=978-0-7923-7668-2 |location=Hamburg, Germany |language=en |doi=10.1007/978-1-4615-0935-6 |ref=harv}}
* {{Cite book |url=http://algs4.cs.princeton.edu/home/ |title=Algorithms |last=Sedgewick |first=Robert |last2=Wayne |first2=Kevin |year=2011 |publisher=Addison-Wesley Professional |isbn=978-0-321-57351-3 |edition=4th |location=Upper Saddle River, New Jersey |language=en |ref=harv |author-link1=罗伯特·塞奇威克}} Condensed web version {{open access}}; book version {{closed access}}.
* {{Cite book |title=算法 |last=Sedgewick |first=Robert |last2=Wayne |first2=Kevin |publisher=[[人民邮电出版社]] |year=2012 |isbn=978-7-115-29380-0 |edition=第4版 |location=北京 |translator=谢路云 |language=zh-Hans-CN |ref={{sfnref|Sedgewick|Wayne|谢路云|2012}} |author-link1=罗伯特·塞奇威克}}
* {{Cite book |title=The C++ programming language |last=Stroustrup |first=Bjarne |year=2013 |publisher=Addison-Wesley Professional |isbn=978-0-321-56384-2 |edition=4th |location=Upper Saddle River, New Jersey |language=en |ref=harv |author-link=Bjarne Stroustrup}}
}}


==外部链接==
* {{Cite Q EtAl|Q81434400}}。该论文内容取自[[英语维基百科]]的对应条目，于2018年经过外部学术[[同行评审]]。
* [https://web.archive.org/web/20161104005739/https://xlinux.nist.gov/dads/HTML/binarySearch.html NIST Dictionary of Algorithms and Data Structures: binary search]
* [https://sites.google.com/site/binarysearchcube/binary-search Comparisons and benchmarks of a variety of binary search implementations in C] {{Webarchive|url=https://web.archive.org/web/20190925012527/https://sites.google.com/site/binarysearchcube/binary-search |date=2019-09-25 }}

{{算法}}
{{DEFAULTSORT:Binary Search}}

[[Category:带有伪代码示例的条目]]
[[Category:搜尋演算法]]
[[Category:二]]