10 二分查找

#coding:utf-8
def binary_search(list, item):
  low = 0
  high = len(list) - 1
  while low <= high:
    mid = (high - low) / 2 + low  # 避免(high + low) / 2溢出
    guess = list[mid]
    if guess > item:
      high = mid - 1
    elif guess < item:
      low = mid + 1
    else:
      return mid
  return None
mylist = [1,3,5,7,9]
print binary_search(mylist, 3)

参考: http://blog.csdn.net/u013205877/article/details/76411718