バイナリサーチ

AOJの問題を解く途中で作ったのでメモしておく。結局使わなくなったけど。
あらかじめソートされているのが前提。見つからないときは None を返す。

def binary_search(lis, x):
    if len(lis) == 0:
        return None
    else:
        i = len(lis) / 2
        if lis[i] == x:
            return x
        elif x < lis[i]:
            return binary_search(lis[:i], x)
        else:
            return binary_search(lis[i+1:], x)

a = range(100000)
print binary_search(a, 3359)
print binary_search(a, 100001)
print binary_search(a, 0)
print binary_search(a, -1)

実行結果：

^o^ > python binary_search.py
3359
None
0
None