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

二分搜索算法

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

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

演算法[编辑]

步驟[编辑]

給予一個包含n個帶值元素的陣列A或是記錄A0 ... An−1,使得A0 ≤ ... ≤ An−1,以及目標值T,還有下列用來搜尋TA中位置的子程式[3]

  1. L為0,Rn− 1。
  2. 如果L > R,則搜尋以失敗告終。
  3. m(中間值元素)為「(L + R) / 2」加上下高斯符號
  4. 如果Am < T,令Lm + 1並回到步驟二。
  5. 如果Am > T,令Rm - 1並回到步驟二。
  6. 當Am = T,搜尋結束;回傳值m

這個疊代步驟會持續透過兩個變數追蹤搜索的邊界。有些實際應用會在演算法的最後放入相等比較,讓比較迴圈更快,但平均而言會多一層疊代[4]

大致匹配[编辑]

以上程序只適用於完全匹配,也就是尋找一個目標值的位置。不過,因為有序陣列的順序性,將二分搜索算法擴展到能適用大致匹配並不是很重要。舉例來說,二分搜索算法可以用來計算一個賦值的排名(或稱,比它更小的元素的數量)、前趨(下一個最小元素)、後繼(下一個最大元素)以及最近鄰。搜尋兩個值之間的元素數目的範圍查詢英语Range query (data structures)可以藉由兩個排名查詢(又稱秩查詢)來執行[5]

  • 排名查詢可以使用調整版的二分搜索來執行。藉由在成功的搜索回傳m,以及在失敗的搜索回傳L,就會取而代之地回傳了比起目標值小的元素數目[5]
  • 前趨和後繼查詢可以藉由排名查詢來執行。一旦知道目標值的排名,其前趨就會是那個位於其排名位置的元素(因為它是小於目標值的最大元素)。其後繼是(陣列中的)下一個元素,或是(非陣列中的)前趨的下一個元素[6]。目標值的最近鄰可能是前趨或後繼,取決於何者較為接近。
  • 範圍查詢也是直接了當的。一旦知道兩個值的排名,不小於第一個值且小於第二個值的元素數量就會是兩者排名的差。這個值可以根據範圍的端點是否算在範圍內,或是陣列是否包含其端點的對應鍵來增加或減少1[7]

复杂度分析[编辑]

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

应用[编辑]

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

示例代码[编辑]

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

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

参考[编辑]

本条目的部分内容翻译自英語維基百科条目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".

外部链接[编辑]