長(zhǎng)時(shí)間不訓(xùn)練，感覺退步很多，今天想練一下動(dòng)態(tài)規(guī)劃發(fā)現(xiàn)需要先寫一個(gè)二分查找，本來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
一個(gè)加速版的二分查找算法
def binsearch(data, key):
'''假定data為單調(diào)非降序列'''
i,j=-1, len(data) #i指向data序列第一個(gè)元素的前一個(gè)位置
#j指向data序列最后一個(gè)元素的后一個(gè)位置
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 #這時(shí)我們可以在j處插入key，同時(shí)不破壞data的有序狀態(tài)
return j #j指向data序列中左數(shù)第一個(gè)值為key的數(shù)據(jù)項(xiàng)