算法图解-二分查找

1. 二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。
   image.png
2. 代码实现如下

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

mylist = [1, 3, 5, 7, 9]
print(binary_search(mylist, 3))
print(binary_search(mylist, -1))

3. 大O表示法是一种特殊的表示法，指出了算法的速度有多快。
   下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
   • O(log n)，也叫对数时间，这样的算法包括二分查找。
   • O(n)，也叫线性时间，这样的算法包括简单查找。
   • O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
   • O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。

   • O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

     
     绘制网格时间.png
   • 算法的速度指的并非时间，而是操作数的增速。
   • 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
   • 算法的运行时间用大O表示法表示。
   • O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。