2020-03-29

对于二分查找，对比递归和非递归的执行效率，理解递归调用中，压栈和弹栈也是有时间开销的。

a=[i for i in range(1,3333)]
#l=left
#r=right
#t=target
#bi=binsearch   because the python has bin()
def bi(l,r,t):
    if l>r:
        return -1
    
    mid=l+r>>1
    if a[mid]==t:
        return mid
    elif a[mid]<t:
        return bi(mid+1,r,t)
    else:
        return bi(l,mid-1,t)

def bin2(l,r,t):
    while l<=r:
        mid =l+r>>1
        if a[mid]==t:
            return mid
        elif a[mid]<t:
            l=mid+1
        else:r=mid-1
    return -1

from timeit import timeit
t3 = timeit('bi(0,3332,3)', 'from __main__ import bi', number=99999)
print(t3)
t4 = timeit('bin2(0,3332,3)', 'from __main__ import bin2', number=99999)
print(t4)

#0.46852131
#0.40458031400000005

对模糊区间查找，随机查找，旋转数组的理解，基于此。

另： 读完一本书，一个知识点也没有增加，应该高兴还是痛苦，还是应该平平淡淡？
另2：推荐一本书《你的灯亮着吗》