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

二分搜索算法

维基百科,自由的百科全书
(重定向自折半搜索算法
跳转至: 导航搜索
二分搜索算法
Binary search into array.png
分類 搜索算法
數據結構 数组
最差時間複雜度 O(log n)
最優時間複雜度 O(1)
平均時間複雜度 O(log n)
最差空間複雜度 迭代:O(1)
递归:O(log n)
(无尾调用消除)

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

复杂度分析[编辑]

时间复杂度
折半搜索每次把搜索区域减少一半,时间复杂度为。(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. 

外部链接[编辑]