長時間不訓(xùn)練，感覺退步很多，今天想練一下動態(tài)規(guī)劃發(fā)現(xiàn)需要先寫一個二分查找，本來python中是有二分查找的bisect模塊，不過想了想還是自己寫一下吧，要不然更銹了：
二分查找算法：
def binsearch(data, key):
i,j=0, len(data)-1
while i<=j:
mid=(i+j)>>1
if data[mid]<key: i=mid+1
elif data[mid]>key: j=mid-1
else: return mid
return -1
一個加速版的二分查找算法
def binsearch(data, key):
'''假定data為單調(diào)非降序列'''
i,j=-1, len(data) #i指向data序列第一個元素的前一個位置
#j指向data序列最后一個元素的后一個位置
while i+1!=j:
mid= (i+j)>>1
if(data[mid]<key):i=mid
else:j=mid
if j==len(data) or data[j]!=key:
return -1 #這時我們可以在j處插入key，同時不破壞data的有序狀態(tài)
return j #j指向data序列中左數(shù)第一個值為key的數(shù)據(jù)項