清风竹林

ぷ雪飘绛梅映残红
   ぷ花舞霜飞映苍松
     ----- Do more,suffer less

二分查找 python

  长时间不训练,感觉退步很多,今天想练一下动态规划发现需要先写一个二分查找,本来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
        
elsereturn 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的数据项





posted on 2008-12-12 11:08 李现民 阅读(989) 评论(0)  编辑 收藏 引用 所属分类: 算法为魂


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理