二分查找第一次出现的位置
scturtle
posted @ 2011年3月17日 15:58
in algorithm
, 1993 阅读
这个简单的问题以前居然没有想过,今天看书才发现二分也是可以做的,顺便用刚学的random库验证一下
# coding: utf-8 from random import * def first(a,x): try: return a.index(x) except ValueError: return -1 def firstbin(a,x): l=0; u=len(a)-1 while True: if l>u: return -1 m=(l+u)/2 if a[l]==x: return l elif a[m]<x: l=m+1 elif a[m]==x: u=m elif a[m]>x: u=m-1 if __name__ == '__main__': cishu=1 while True: a=[] for i in range(randint(1,10)): a.extend(range(100)) a=sample(a,randint(0,len(a))) a.sort() x=randint(0,99) print cishu, cishu+=1 if first(a,x)==firstbin(a,x): print 'OK' #print x,a else: print 'OOH!' print a,x break
update:
编程珠玑(中文第2版)88-90页上给出的另两种:
def binsearch(a,x): l=-1;u=len(a) while l+1!=u: # invariant: x[l]<t && x[u]>=t && l<u m=(l+u)/2 if a[m]<x: l=m else: u=m # assert: l+1=u && x[l]<t && x[u]>=t p=u if p>=len(a) or a[p]!=x: p=-1 return p
def binsearch(a,x): if len(a)==0: return -1 i=max1(len(a)) print len(a),i l=-1 if a[i-1]<x: l=len(a)-i while i!=1: # invariant: x[l]<t && x[l+i]>=t && i=2^j i=i/2 if a[l+i]<x: l=l+i # assert: i==1 && x[l]<t && x[l+i]>=t p=l+1 print p if p>=len(a) or a[p]!=x: p=-1 return p
循环不变式 断言 和 脚手架是好东西
书上说第二个的循环展开非常经典高效