二分查找是一种算法，它的输入是一个有序的元素列表（必须有序）。如果查找的元素包含再列表中，二分查找返回其位置，否则返回NULL。
对于，使用二分查找包含n个元素的列表，最多需要log2 n步，但是简单查找需要最多n步。
下面的代码，输入一个有序数组，以及要查找的数，会自动返回是否在数组中存在该数字。

#binary_search.py
def binary_search(list, item):
  low = 0
  high = len(list)-1
  while low <= high:
    mid = (low + high)/2
    guess = list[mid]
    if guess == item:
      return mid
    if guess > item:
      high = mid -1
    else:
      low = mid + 1
  return None

时间复杂度

时间复杂度O(n)表示了算法运行时间的增速。下面是从快到慢顺序列出了5种经常碰到的大O运行时间。

O(log n): 对数时间，包含了二分查找
O(n): 线性时间，包含了简单查找
O(n * log n): 快速排序，速度较快的排序算法
O(n^2): 选择排序，速度较慢的排序算法
O(n!): 旅行商问题的解决方案，非常慢的算法

旅行商问题

当一个商人要去5个城市，同时要确保路径最短。那么总共有120种排列顺序（5！）。每增加一个城市，就要增加大量的排列组合。时间复杂度就是O(n!)。

小结

二分查找速度比简单查找快的多
O(log n)比O(n)要快很多，需要搜索的元素越多，前者比后者就快的越多。
算法运行时间是从其增速的角度度量的。
算法运行时间用大O表示法表示。