长时间不训练，感觉退步很多，今天想练一下动态规划发现需要先写一个二分查找，本来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为单调非降序列'''
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的有序状态
return j #j指向data序列中左数第一个值为key的数据项