文章概述
- 二分查找法介绍
- 简单查找与二分查找对比
二分查找
二分查找算法主要思想：在有序列表中查找指定元素，先从列表的中间查找，比较中间元素与目标元素的大小，然后在剩余的一半列表中继续这样查找，每次查找都能过滤掉一半元素。最多需要查找logn次，那么时间复杂度是O(logn)。记住：列表必须有序。
例子：在列表1-100直接查找目标元素60
- 找到中间元素50，与60比较，目标元素大于中间元素，那么在50-100间查找
- 50到100中间元素75，依次循环，直到找到60为止。
python实现：
def binary_search(l, value):
'''
l是有序列表，value是目标元素
'''
start = 0
end = len(l) - 1
t = 0 # 查找次数
while end >= start:
t += 1
mid = int((start+end)/2)
guess = l[mid]
if guess < value:
start = mid + 1
elif guess > value:
end = mid - 1
else:
print("查找次数%d" % t)
return mid
return False
二分查找效率
二分查找算法的效率如何，我们做个试验与简单查找来对比
我们首先写个时间装饰器来记录算法运行的时间
def timeit(func):
"""打印时间"""
def new_func(self, *args, **kwargs):
now = time.time()
ret = func(self, *args, **kwargs)
ms = 1000 * (time.time() - now)
print("%s() in %.3fms.", func.__name__, ms)
return ret
return new_func
简单查找算法
@timeit
def single(l,value):
t = 0 # 查找次数
for i,v in enumerate(l[::-1]):
t += 1
if v == value:
print("查找次数%d" % t)
return i
return False
- 列表长度为1000
简单查找：最大次数1000，最差时间0.063ms.
二分查找：最大次数10，最差时间0.034ms. - 列表长度为100000
简单查找：最大次数100000，最差时间6.096ms.
二分查找：最大次数17，最差时间0.028ms. - 列表长度为1000000
简单查找：最大次数1000000，最差时间66.096ms.
二分查找：最大次数17，最差时间0.042ms.
可见，简单查找次数和时间呈线性增长，列表长度越大，消耗时间和次数越多，但适用条件广泛，类似list的index方法。而二分查找呈对数增长，列表长度越大，消耗时间和次数增加不明显，但是二分查找适用条件不广泛，必须是有序的列表
image.png
