Python 实现的Binary Search 算法以及效率的对比

lichengcom2009

　　最近用Python3.2,3实现了一下Binary Search算法,同时看到网上有关于程序执行时间统计的代码段,于是就加到了程序里

import random
import functools
import timeit
original=[]
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));
#Main
if __name__=="__main__":
compare_search_effective();