这个简单的问题以前居然没有想过,今天看书才发现二分也是可以做的,顺便用刚学的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

循环不变式 断言 和 脚手架是好东西

书上说第二个的循环展开非常经典高效