二进制搜索python

Question

我在争取时间 不同大小的二进制搜索。我只得到2097152与这个计划。我是python新手。我知道缩进在python中是至关重要的。有压痕吗？谢谢

import time
def bsearch(a,first,last,key):
    if first>last:
        #print "not found"
            return
    mid=(first+last)//2
    if key==a[mid]:
        #print "found"
            return
    elif key>a[mid]:
        bsearch(a,mid+1,last,key)
    else:
        bsearch(a,first,mid-1,key)

a=[1]*2097152
sizes=[128,512,2048,8192,32768,131072,524288,2097152]
for i in range(0,8):
    for j in range(0,sizes[i]):
        a[j]=j
start=time.time()
for k in range(0,20000):
    bsearch(a,0,j-1,j)
stop=time.time()
print ("time for size "+str(j)+" is: "+str((stop-start)*1000))

Answer 1

from timeit import timeit

for length in [128,512,2048,8192,32768,131072,524288,2097152]:
    l = list(range(length+1))
    command = 'bsearch(l, 0, length, length)'
    print('{:<23} seconds for {}'.format(timeit(command, globals=globals(), number=2000), length))

下面的版本使用^{}来度量在给定大小的列表上执行bsearch2000次所需的时间。在我的机器上结果是

0.005647999999382591    seconds for 128
0.007602000000588305    seconds for 512
0.009716999999909604    seconds for 2048
0.010829999999259599    seconds for 8192
0.012752000000546104    seconds for 32768
0.0143049999996947      seconds for 131072
0.01644899999973859     seconds for 524288
0.020023000000037428    seconds for 2097152

编辑：

如果您使用的是Python版本<；3.5，globals在timeit中不可用。您可以改为import从__main__

from timeit import timeit

for length in [128,512,2048,8192,32768,131072,524288,2097152]:
    l = list(range(length+1))
    command = 'bsearch(l, 0, length, length)'
    setup = 'from __main__ import bsearch, l, length'
    print('{:<23} seconds for {}'.format(timeit(command, setup=setup, number=2000), length))