二分查找

二分查找是一种快速的查找算法。

引言

 试想一下,你的一个朋友和你玩游戏,他心里想一个100以内的整数,你每猜一次他会告诉你结果是大了还是小了。
那么这时候用什么方法最快呢?总不可能一个个地试吧?
如果一个个试的话,那最糟的情况下你可能需要猜100次才能猜中。
而二分查找正是解决这种问题的一种简便方法。

二分查找

 二分查找的原理是根据返回值来判断。比如你第一次猜的是50,那么根据你朋友的反馈,你便可以排除另一半的结果了。

P.S.使用二分查找的对象必须是有序的。

代码示例

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bin_search(data_list, val):
low = 0 # 最小数下标
high = len(data_list) - 1 # 最大数下标
while low <= high:
mid = (low + high) // 2 # 中间数下标
if data_list[mid] == val: # 如果中间数下标等于val, 返回
return mid
elif data_list[mid] > val: # 如果val在中间数左边, 移动high下标
high = mid - 1
else: # 如果val在中间数右边, 移动low下标
low = mid + 1
return # val不存在, 返回None
ret = bin_search(list(range(1, 10)), 3)
print(ret)

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var Arr = [3, 5, 6, 7, 9, 12, 15];
function binary(find, arr, low, high) {
if (low <= high) {
if (arr[low] == find) {
return low;
}
if (arr[high] == find) {
return high;
}
var mid = Math.ceil((high + low) / 2);
if (arr[mid] == find) {
return mid;
} else if (arr[mid] > find) {
return binary(find, arr, low, mid - 1);
} else {
return binary(find, arr, mid + 1, high);
}
}
return -1;
}
binary(15, Arr, 0, Arr.length - 1);