二分查找
上一小节说的线性查找针对的是无序序列,假如一个序列已经有序了呢,我们还需要从头找到尾吗?当然不用,折半(二分)是一种经典思想。日常生活中还有哪些经典的二分思想呢?
- 猜数字游戏
- 有些民间股神,告诉一堆人某个股票会涨,告诉另一半人会跌。后来真涨了,慢慢又告诉信了他的一半人另一个股票会涨,另一半说会跌。就这样韭菜多了总有一些人信奉他为股神…...
举例:
def binary_search(sorted_array, val):
if not sorted_array:
return -1
beg = 0
end = len(sorted_array) - 1
while beg <= end:
mid = int((beg + end) / 2) # beg + (end-beg)/2, 为了屏蔽 python 2/3 差异我用了强转
if sorted_array[mid] == val:
return mid
elif sorted_array[mid] > val:
end = mid - 1
else:
beg = mid + 1
return -1
def test_binary_search():
a = list(range(10))