User:Viztor/Binary search algorithm

维基百科,自由的百科全书
Viztor/Binary search algorithm
二叉搜索算法的演示,目标值为7
概况
复杂度
相关变量的定义

二分搜索(也称为折半搜索算法,对数搜索,或二进切分)是计算机科学中的一种在有序数组中搜索的搜索算法。二分搜索将目标值与数组的中间元素进行比较。[1][2] 如果不相等,则去掉目标值不可能存在的一半,并在另一半上进行搜索,再次将中间元素以目标值进行比较,重复这一过程,直到找到目标值。 如果搜索结束时剩下的一半为空,则目标不在数组中。 尽管想法简单,但实现时,则需要特别注意其退出条件和中点的计算。

在最坏情况下,二分搜索以对数时间运行,进行 次比较操作(是数组中的元素数,是大 o 符号,是对数)。 二分搜索需要恒定的空间,这意味着该算法所占的空间对于任意数目元素数组都是相同的。[3] 二分搜索只能用于有序数组。除了小数组外,二分搜索比线性搜索更快。尽管专门用于快速搜索的数据结构可以更有效(如哈希表),但二分搜索更广泛适用各种问题。

二进制搜索有许多不同分支。 比如:分级级联加速多个数组中相同值的二进制搜索。 分数级联有效地解决了计算几何和许多其他字段中的一些搜索问题。 指数搜索将二进制搜索扩展到无界的列表。 二叉查找树和 B-tree 数据结构是基于二进制搜索的。

算法[编辑]

对排序数组进行二进制搜索。 二进制搜索首先将数组的中间元素与目标值进行比较。 如果目标值与中间元素相匹配,则返回其在数组中的位置。 如果目标值小于中间元素,则搜索继续在数组的下半部分。 如果目标值大于中间元素,则搜索继续在数组的上半部分。 通过这样做,算法消除了目标值不能在每个迭代中隐藏的一半。

程序[编辑]

Given an array of elements with values or records sorted such that , and target value , the following subroutine uses binary search to find the index of in .[4]

  1. Set to and to .
  2. If , the search terminates as unsuccessful.
  3. Set (the position of the middle element) to the floor of , which is the greatest integer less than or equal to .
  4. If , set to and go to step 2.
  5. If , set to and go to step 2.
  6. Now , the search is done; return .

This iterative procedure keeps track of the search boundaries with the two variables and . The procedure may be expressed in pseudocode as follows, where the variable names and types remain the same as above, floor is the floor function, and unsuccessful refers to a specific value that conveys the failure of the search.[4] [[Category:二]] [[Category:搜尋演算法]] [[Category:Webarchive模板wayback链接]] [[Category:CS1匈牙利文来源 (hu)]] [[Category:Pages with unreviewed translations]]

  1. ^ 空引用 (帮助) 
  2. ^ 埃里克·韦斯坦因. Binary search. MathWorld. 
  3. ^ Flores, Ivan; Madpis, George. Average binary search length for dense ordered lists. Communications of the ACM. 1 September 1971, 14 (9): 602–603 [29 June 2018]. Bibcode:1985CACM...28...22S. ISSN 0001-0782. doi:10.1145/362663.362752. 
  4. ^ 4.0 4.1 Knuth 1998,§6.2.1 ("Searching an ordered table"), subsection "Algorithm B".