本页使用了标题或全文手工转换

二分搜索算法

维基百科,自由的百科全书
(重定向自折半搜索算法
跳转至: 导航搜索
二分搜索算法
Binary search into array.png
分类 搜索算法
数据结构 数组
最坏时间复杂度
最优时间复杂度
平均时间复杂度
空间复杂度 迭代:
递归:
(无尾调用消除)

计算机科学中,二分搜索英语:binary search),也称折半搜索英语:half-interval search[1]对数搜索英语:logarithmic search[2],是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

算法[编辑]

步骤[编辑]

给予一个包含个带值元素的数组或是记录,使,以及目标值,还有下列用来搜索中位置的子程序[3]

  1. 如果,则搜索以失败告终。
  2. (中间值元素)为
  3. 如果,令并回到步骤二。
  4. 如果,令并回到步骤二。
  5. ,搜索结束;回传值

这个迭代步骤会持续通过两个变量追踪搜索的边界。有些实际应用会在算法的最后放入相等比较,让比较循环更快,但平均而言会多一层迭代[4]

大致匹配[编辑]

以上程序只适用于完全匹配,也就是查找一个目标值的位置。不过,因为有序数组的顺序性,将二分搜索算法扩展到能适用大致匹配并不是很重要。举例来说,二分搜索算法可以用来计算一个赋值的排名(或称,比它更小的元素的数量)、前趋(下一个最小元素)、后继(下一个最大元素)以及最近邻。搜索两个值之间的元素数目的范围查询英语Range query (data structures)可以借由两个排名查询(又称秩查询)来运行[5]

  • 排名查询可以使用调整版的二分搜索来运行。借由在成功的搜索回传,以及在失败的搜索回传,就会取而代之地回传了比起目标值小的元素数目[5]
  • 前趋和后继查询可以借由排名查询来运行。一旦知道目标值的排名,其前趋就会是那个位于其排名位置的元素(因为它是小于目标值的最大元素)。其后继是(数组中的)下一个元素,或是(非数组中的)前趋的下一个元素[6]。目标值的最近邻可能是前趋或后继,取决于何者较为接近。
  • 范围查询也是直接了当的。一旦知道两个值的排名,不小于第一个值且小于第二个值的元素数量就会是两者排名的差。这个值可以根据范围的端点是否算在范围内,或是数组是否包含其端点的对应键来增加或减少1[7]

复杂度分析[编辑]

时间复杂度
折半搜索每次把搜索区域减少一半,时间复杂度为。(n代表集合中元素的个数)
空间复杂度
。虽以递归形式定义,但是尾递归,可改写为循环。

应用[编辑]

除直接在一个数组中查找元素外,可用在插入排序中。

示例代码[编辑]

// 递归版本
int binary_search(const int arr[], int start, int end, int khey) {
	if (start > end)
		return -1;

	int mid = start + (end - start) / 2; //直接平均可能會溢位,所以用此算法
	if (arr[mid] > khey)
		return binary_search(arr, start, mid - 1, khey);
	if (arr[mid] < khey)
		return binary_search(arr, mid + 1, end, khey);
	return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
}
// while循环
int binary_search(const int arr[], int start, int end, int khey) {
	int mid;
	while (start <= end) {
		mid = start + (end - start) / 2; //直接平均可能會溢位,所以用此算法
		if (arr[mid] < khey)
			start = mid + 1;
		else if (arr[mid] > khey)
			end = mid - 1;
		else
			return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
	}
	return -1;
}
//javascript版本
Array.prototype.binary_search = function(low, high, khey) {
	if (low > high)
		return -1;
	var mid = parseInt((high + low) / 2);
	if (this[mid] > khey)
		return this.binary_search(low, mid - 1, khey);
	if (this[mid] < khey)
		return this.binary_search(mid + 1, high, khey);
	return mid;
};
# python版本
def binary_search(arr,start,end,hkey):
	if start > end:
		return -1
	mid = start + (end - start) / 2
	if arr[mid] > hkey:
		return binary_search(arr, start, mid - 1, hkey)
	if arr[mid] < hkey:
		return binary_search(arr, mid + 1, end, hkey)
	return mid
# python版本,while循环
<syntaxhighlight lang="python3">
def binary_search(arr, start, end, hkey):
	while start <= end:
		mid = start + (end - start)/2
		if arr[mid] < hkey:
			start = mid + 1
		elif arr[mid] > hkey:
			start = mid - 1
		else:
			return mid
</syntaxhighlight>
//c#版本
        static int binary_search(int[] arr, int start, int end, int khey)
        {
            int mid;
            while (start <= end)
            {
                mid = (start + end) / 2;
                if (arr[mid] < khey)
                    start = mid + 1;
                else if (arr[mid] > khey)
                    end = mid - 1;
                else
                    return mid; 
            }
            return -1;
        }

参考[编辑]

本条目的部分内容翻译自英语维基百科条目Binary search algorithm英语Binary search algorithm并以知识共享-署名-相同方式共享3.0协议授权使用。原文作者列表请参阅其页面历史
  • Sahni, Sartaj. Data Structures, Algorithms, and Applications in C++. McGraw2-Hill. 1998. ISBN 978-0072362268. 
  1. ^ Willams, Jr., Louis F. A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference: 95–101. 1975. doi:10.1145/503561.503582. 
  2. ^ Knuth 1998,§6.2.1 ("Searching an ordered table"), subsection "Binary search".
  3. ^ Knuth 1998,§6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
  4. ^ Bottenbruch, Hermann. Structure and Use of ALGOL 60. Journal of the ACM. 1962, 9 (2): 161–211.  Procedure is described at p. 214 (§43), titled "Program for Binary Search".
  5. ^ 5.0 5.1 Sedgewick & Wayne 2011,§3.1, subsection "Rank and selection".
  6. ^ Goldman & Goldman 2008, pp. 461–463.
  7. ^ Sedgewick & Wayne 2011,§3.1, subsection "Range queries".

外部链接[编辑]