算法 - 二分法

二分法要求必须有序，时间复杂度最大为$O(log(n))$，其中$log$指$lo{g}_2$。

import time def binary_search(list_,item): low=0 high=len(list_)-1 while low<=high: mid=int((low+high)/2) guess=list_[mid] if guess==item: return mid if guess>item: high=mid-1 else: low=mid+1 return None def common_search(list_,item): for i in range(len(list_)): if item==list_[i]: return i return None my_list=list(range(100000000)) startTime=time.time() print(binary_search(my_list,100000000-1)) print(binary_search(my_list,-1)) endTime=time.time() print("binary search",endTime-startTime) startTime=time.time() print(common_search(my_list,100000000-1)) print(common_search(my_list,-1)) endTime=time.time() print("common search",endTime-startTime)

以上是二分法和顺序法查找的时间对比关系。同时注意，形参位置不能直接写list，如果想要区别一下，可以写list_，这也是后缀单下划线的用法之一。