二分查找是一个很常用的算法，用于在有序数组中查找指定元素的索引
先来看版本一：
1 def bin_search(lst, a): 2 """ 3 二分查找函数 4 lst: 序列，默认升序 5 a: 要查找的值 6 返回值: a的索引，找不到返回None 7 """ 8 if a == lst[len(lst) // 2]: 9 return len(lst) // 2 10 elif a < lst[len(lst) // 2]: 11 bin_search(lst[:len(lst) // 2], a) 12 else: 13 bin_search(lst[(len(lst)+1) // 2:], a)
这种方法存在以下几点错误：
（1）第11、13行递归时没有返回值，这是一个很低级的错误！
（2）此算法中对列表进行了切片，切片之后索引就变了，返回的索引就不是原列表的索引
版本二：
1 def bin_search(lst, num, start=None, end=None): 2 """ 3 二分查找 4 :param lst: 列表 5 :param num: 目标元素 6 :param start: 查找的起始位置 7 :param end: 查找的终止位置 8 :return: 返回索引，找不到返回None 9 """ 10 start = start if start else 0 11 end = end if end else len(lst)-1 12 mid = (end - start)//2 + start 13 if start > end: 14 return None 15 elif num == lst[mid]: 16 return mid 17 elif num < lst[mid]: 18 bin_search(lst, num, start, mid-1) 19 else: 20 bin_search(lst, num, mid+1, end)
二分查找的效率是很高的，因为每调用一次查找范围就减半，因此只需要很少的次数就可以找到目标元素。
为了查看函数调用的次数，我写了一个简单的装饰器来输出函数递归调用的次数，完整代码如下：
1 import time 2 3 def call_num(func): 4 """ 5 此装饰器函数用于计算函数调用次数 6 :param func: 7 :return: 8 """ 9 num = 0 10 11 def inner(*args, **kwargs): 12 nonlocal num 13 ret = func(*args, **kwargs) 14 num += 1 15 print("function called number:", num) 16 return ret 17 return inner 18 19 20 @call_num 21 def bin_search(lst, num, start=None, end=None): 22 """ 23 二分查找 24 :param lst: 列表 25 :param num: 目标元素 26 :param start: 查找的起始位置 27 :param end: 查找的终止位置 28 :return: 返回索引，找不到返回None 29 """ 30 start = start if start else 0 31 end = end if end else len(lst)-1 32 mid = (end - start)//2 + start 33 if start > end: 34 return None 35 elif num == lst[mid]: 36 return mid 37 elif num < lst[mid]: 38 bin_search(lst, num, start, mid-1) 39 else: 40 bin_search(lst, num, mid+1, end) 41 42 l1 = [] 43 44 for i in range(100000000): 45 l1.append(i) 46 start_time = time.time() 47 print(bin_search(l1, 83374292)) 48 end_time = time.time() 49 print(end_time-start_time)
执行结果
function called number: 1 function called number: 2 function called number: 3 function called number: 4 function called number: 5 function called number: 6 function called number: 7 function called number: 8 function called number: 9 function called number: 10 function called number: 11 function called number: 12 function called number: 13 function called number: 14 function called number: 15 function called number: 16 function called number: 17 function called number: 18 function called number: 19 function called number: 20 function called number: 21 function called number: 22 function called number: 23 function called number: 24 function called number: 25 83374292 0.008976936340332031
可见查找1亿条数据只需要0.009秒，函数调用了25次，是相当快的