Python 实现的Binary Search 算法以及效率的对比
最近用Python3.2,3实现了一下Binary Search算法,同时看到网上有关于程序执行时间统计的代码段,于是就加到了程序里
import randomimport functoolsimport timeitoriginal=[]target=0;def binary_search(target,seq=[],lowerindex=0,upperindex=None): "for binary search" middleIndex=int((upperindex+lowerindex)/2) if middleIndex==lowerindex: print("not found",target) else: if seq[middleIndex]==target: print("binary search found",seq[middleIndex]) print("binary search index is:", middleIndex+1) elif seq[middleIndex]<target: binary_search(target,seq,middleIndex,upperindex) else: binary_search(target,seq,lowerindex,middleIndex)def larget_number_search_binarysearch(): print("target number is:",target); sortseq=original[:] sortseq.sort() binary_search(target,sortseq,0,len(sortseq));def larget_number_search(): for index,temp in enumerate(original): if target==temp: print("iterator search found", target); print("iterator index is:",index+1); break;def compare_search_effective():"比较二分查找法与迭代查找法的效率" global original, target original=[random.randint(0,100000000) for x in range(1000000000)] target=random.choice(original); #通过timeit.Timer统计发放的执行时间 binary_search_time = timeit.Timer('larget_number_search_binarysearch()',"from __main__ import larget_number_search_binarysearch") # v3 iterator_search_time=timeit.Timer('larget_number_search()',"from __main__ import larget_number_search") # v3 print ("binary search time:",binary_search_time.timeit(1),"\n"); print ("iterator search time:",iterator_search_time.timeit(1));#Mainif __name__=="__main__": compare_search_effective();