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

二分查找

二分查找

分类 数据结构 时间复杂度 最优时间复杂度 平均时间复杂度 空间复杂度
搜索算法 数组 O(log n) О(1) O(log n) 迭代:O(1), 递归:O(log n)

代码范例

C语言

1
2
3
4
5
6
7
8
9
10
11
12
// 递归版本
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; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 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;
}

Python

1
2
3
4
5
6
7
8
9
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

JavaScript

1
2
3
4
5
6
7
8
9
10
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;
};

复杂度分析

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

参考:https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95