茶年 · 中文维基百科

二分搜尋

Wikipedia · 2026-07-18 维基百科 👁 1 阅读

{{各地中文名
| t = 1
| name =
| cn =
| hk =
二分查找（）是用于查找有序数组中目标值位置的搜索算法。二分查找比较目标值与数组中间元素的大小，如果两者不相等，则会舍弃不可能包含目标值的那一半区间，然后在剩余区间重复此过程：每次选取新的中间元素并与目标值比较，直至找到目标或区间为空。若区间为空，则说明目标值不存在。

二分查找在下的时间复杂度为对数级别，即需做O(\log n)次比较，其中n是数组元素的数量。除规模较小的数组外，二分查找通常比线性搜索更快。二分查找的搜索效率可能不及哈希表等数据结构，但其还可用于查找最接近目标值的上界或下界，即使目标值不在数组中。

二分查找有许多其他形式。例如，能加快在多个数组中查找同一数值的速度，还能高效地解决计算几何等领域的搜索问题；则将搜索范围扩展至无界列表。二叉搜索树和B树等数据结构的实现也基于二分查找原理。

算法
二分查找适用于有序数组。其首先比较数组中间的元素与目标值：如果目标值与该元素匹配，则返回其在数组中的位置；如果目标值小于该元素，则在数组较小的那一半中继续查找；如果目标值大于该元素，则在数组较大的那一半中继续查找。通过这种方法，每次迭代都能将搜索范围缩小一半。

过程
给定包含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中的索引。

令L为 0，R为n-1。

如果L>R，则搜索失败并终止。

令m（中间元素的位置）为\frac{L+R}{2}的向下取整值，即不大于\frac{L+R}{2}的最大整数。

如果A_m ，则令L为m+1，回到步骤2。

如果A_m > T，则令R为m-1，回到步骤2。

如果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
R := m − 1
else:
return m
return unsuccessful

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

另一过程
上述过程中，每次迭代都会检查中间元素m是否等于目标值T。而在其他一些实现中，此检查仅在最后剩余一个元素（即L=R）时执行，而每次迭代时不再执行比较。和前述过程相比，此方式平均多一轮迭代，但每轮迭代时少做一次比较。

于1962年首次发表了省略此检查的实现。

运行时间和缓存使用
在分析二分查找的性能时，还需考虑比较两个元素的所需的时间。整数和字符串的比较时间通常与其编码长度（一般以位数表示）呈线性关系。假设逐位比较，与32位无符号整数相比，64位无符号整数的比较时间至多是前者最坏情况（即两个整数相同）的两倍。如果元素的编码长度较大（例如大整数类型或长字符串），比较操作的开销会显著增加。此外，比较浮点数（实数在计算机中最常用的表示方式）通常也比整数和短字符串耗时更多。

多数计算机架构中，CPU内部配有独立于内存（RAM）的硬件缓存，容量极小但速度极快。因此，考虑到访问局部性，多数CPU会存储最近访问的内存地址及其附近地址的数据。就数组而言，CPU访问某个元素时，会同时缓存该元素以及在RAM中与之相邻的元素，从而更快地顺序访问索引相近的数组元素。然而，二分查找每次跳跃到数组中点，内存跨度往往较大，不像线性搜索或哈希表的线性探测那样具有良好局部性。因此查找较大数组时，实际耗时可能略高于理论预期。此外，有序数组上还能高效完成一些操作，例如获取最小值和最大值。

线性搜索
线性搜索是简单的搜索算法，其逐个检查记录，直到找到目标值为止。线性搜索可在链表上实现，其插入和删除操作比数组更快。对于有序数组，除非数组很短，否则二分查找通常比线性搜索更快。不过二分查找需要提前对数组排序，{{Efn|Knuth（1998）对这两种搜索算法的运行时间做了形式化分析。在Knuth设计的上，对于成功搜索，二分查找平均耗时为18 \log n - 16个单位；而在数组末尾加入的线性搜索平均耗时为1.75n + 8.5 - \frac{n \text{ mod } 2}{4n}个单位。线性搜索的计算量很少，故初始复杂度较低，但随规模增长，其复杂度很快便会超过二分查找。在MIX计算机上，只有当n > 44时，二分查找的性能才会超过带哨兵的线性搜索。}}所有基于元素比较的排序算法（例如快速排序和归并排序），最坏情况下都至少需要做O(n \log n)次比较。与线性搜索不同，二分查找还能高效地进行近似匹配。此外，在有序数组中，查找最大或最小元素等操作可以高效完成，而无序数组则无法做到。

二叉树
的搜索算法类似于二分查找]]二叉搜索树是基于二分查找原理构建的二叉树数据结构。树中元素按序排列，每个元素都可使用类似二分查找的方法执行搜索，其平均时间复杂度为对数级别。二叉搜索树的插入和删除操作平均也为对数时间，通常比有序数组插入和删除的线性时间更快。同时，二叉树也保留了有序数组的所有操作能力，包括范围查询和近似查询。但哈希表只在搜索失败时告知目标不存在，而不能给出邻近值的信息，因此不适合近似匹配，若执行查找下一个较小值、下一个较大值或者最近的键值等操作，效果不佳。二分查找则非常适合近似匹配，且能在对数时间内完成。此外，诸如查找最大或最小元素等操作，在有序数组上可高效完成，而哈希表无法轻易做到。

对于近似结果，布隆过滤器是基于哈希函数的概率型数据结构，其使用位数组和多个哈希函数对键编码，以存储键集合。多数情况下，布隆过滤器比位数组的空间利用率更高，且速度也不会明显变慢：若使用k个哈希函数，成员查询仅需O(k)时间。不过，布隆过滤器存在误报问题。{{Efn|一些版本改进了布隆过滤器，优化了其复杂度或支持删除操作。例如，布谷鸟过滤器利用技术，实现了这些优势。

其他数据结构
某些情况下，一些数据结构可能在搜索操作和其他适用于有序数组的操作上比二分查找更高效。对于搜索、近似匹配及有序数组上的一些操作，可以使用专门的数据结构，如van Emde Boas树、、字典树（）、位数组。这些数据结构通常只有在特定属性的键值（如小整数键值）上更快，否则可能会导致时间或空间效率降低。

对于较小的数组，插值搜索由于有额外的计算开销，其速度通常会比二分查找慢。尽管插值搜索的时间复杂度增长更慢，但只有在数组规模较大时，这种优势才能抵消额外计算所需的开销。

分数级联
分数级联是用于在多个有序数组中快速搜索同一元素的技术。如果逐个搜索每个数组，时间复杂度为O(k \log n)，其中k为数组个数。分数级联在每个数组中存储关于元素在其他数组位置的信息，将时间复杂度降至O(k + \log n)。

分数级联最初是为了解决计算几何中的多种搜索问题而开发的。后来，它也被应用于数据挖掘和互联网协议（IP）路由中。

噪声二分查找
噪声二分查找用于处理算法无法可靠地比较数组元素的情况，即比较每对元素大小时，都有一定概率出错。噪声二分查找可在给定的概率下确定目标元素正确的位置，这一概率控制着结果的可靠性。任何噪声二分查找过程期望比较次数至少为(1 - \tau)\frac{\log_2 (n)}{H(p)} - \frac{10}{H(p)}，其中H(p) = -p \log_2 (p) - (1 - p) \log_2 (1 - p) 为，\tau表示最终输出错误位置的概率。噪声二分查找问题也可视作的特例，即基于的一种版本，其中回答可能会出错。

量子二分查找
经典计算机执行二分查找时，在最坏情况下的迭代次数严格为\lfloor \log_2 n + 1 \rfloor。量子算法执行二分查找的查询次数（对应经典算法的迭代次数）仍然与\log_2 n成正比，但常数因子小于1，因此在量子计算机上具有更低的时间复杂度。任何精确（即总能返回正确结果）的量子二分查找算法，最坏情况下至少需要\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n次查询（其中\ln为自然对数）。目前已经发现一种精确的量子二分查找算法，在最坏情况下的查询次数为4 \log_{605} n \approx 0.433 \log_2 n。相比之下，格罗弗算法是用于搜索无序列表的最优量子算法，所需的查询次数为O(\sqrt{n})。

历史
排序列表元素以提高查找效率，这一思想古已有之。目前已知最早的实例是约公元前200年巴比伦的「Inakibit-Anu」泥板，其包含约500个六十进制的数字及其倒数，数字按字典序排列，以便更快地找到特定的元素。此外，爱琴海诸岛上也发现了一些按照姓名首字母排序的人名列表。1286年完成的拉丁语词典《》，首次给出了完整的字母排序规则，而不仅仅是依照单词前几个字母排序。

1946年，约翰·莫奇利在（一门计算机科学领域的奠基性课程）中首次提及了二分查找。1957年，发表了首个插值搜索算法。早期的二分查找算法均只能用于长度为2的幂次减一的数组。直至1960年，德里克·亨利·莱默提出适用于任意长度数组的二分查找算法。1962年，在ALGOL 60语言中实现了另一种二分查找版本，将判断相等的比较操作放在末尾，虽使平均迭代次数增加了一次，但每次迭代所需的比较次数减少至一次。

实现问题
乔恩·本特利在为职业程序员开设的一门课程中布置了二分查找的练习，发现90%的学生在数小时后仍未给出正确解答，主要问题是算法实现有误而无法运行，或是在极少数邊緣案例下返回错误答案。1988年发表的一项研究显示，二十本教材中只有五本给出了准确的二分查找代码。此外，本特利自身在1986年出版的《编程珠玑》一书中给出的二分查找实现存在溢出错误，这个错误二十余年未被发现。Java编程语言库中的二分查找实现也存在相同的溢出问题，且该问题持续了九年多。

在实际编程中，表示索引的变量通常是固定大小的整数。因此在处理非常大的数组时，可能会导致算术溢出。如果使用\frac{L+R}{2}计算中点，即使L和R的值都在所用数据类型的表示范围内，L+R的值仍可能会超过范围。如果L和R都是非负数，可以通过计算L+\frac{R-L}{2}来避免这种情况。

如果循环的退出条件定义不正确，可能会导致无限循环。当L超过R时，表示搜索失败，必须返回失败的信息。另外，循环应在找到目标元素时退出；若不这么做，那么在循环结束后，必须检查是否成功找到目标元素。本特利发现，大多数在实现二分查找时出错的程序员，都是退出条件出了错。

  • C++的标准库中提供了binary_search()、lower_bound()、upper_bound()、equal_range()函数。
  • D语言的标准库Phobos在std.range模块中提供了SortedRange类型（由sort()和assumeSorted()函数返回），该类型包含contains()、equaleRange()、lowerBound()、trisect()方法，这些方法默认对提供随机访问的范围使用二分查找技术。
  • COBOL提供了SEARCH ALL动词，用于对COBOL有序表执行二分查找。
  • Go的sort标准库包包含Search、SearchInts、SearchFloat64s、SearchStrings函数，分别实现了通用的二分查找，以及针对整数、浮点数、字符串切片的特定实现。
  • Java在标准java.util包的和类中提供了一组重载的binarySearch()静态方法，用于对Java数组和List（列表）执行二分查找。
  • Microsoft的.NET Framework 2.0在其集合基类中提供了二分查找算法的静态泛型版本，例如System.Array的BinarySearch(T[] array, T value)方法。
  • 对于Objective-C，Cocoa框架在Mac OS X 10.6及以上版本中提供了[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:]方法；苹果的 C框架也包含[https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/Reference/reference.html#//apple_ref/c/func/CFArrayBSearchValues CFArrayBSearchValues()]函数。
  • Python提供了模块bisect，在插入元素后仍能保持列表的有序状态，而无需每次插入元素后都对列表排序。
  • Ruby的Array类包含带有内置近似匹配的bsearch方法。
  • Rust的切片原始类型提供了binary_search()、binary_search_by()、binary_search_by_key()、partition_point()方法。

参见
*

注释和参考文献
注释
引用
来源
外部链接

#带有伪代码示例的条目 #搜尋演算法 #2

评论 (0)

  • 还没有评论，来抢沙发吧。