场景

假设要在电话薄中查找一个以 L 开始的电话号码，可以从开头开始翻页查找，但是也可以直接从中间开始，因为你知道 以 L 开始的名字在电话簿中间， 又或者小时候字典查找以 M 开始的单词，我们也可以从中间开始。这一类查找问题，都可以使用 二分查找 来解决上述问题

前提条件

二分查找要求输入的是一个有序的元素列表。

Python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def binary_search(array_list, item):
    """
    :param array_list 有序的列表元素
    :param item 想要查询的元素
    :return int 返回这个元素在序列中的索引位置
    """
    low = 0
    high = len(array_list) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = array_list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

运行时间

程序运行都会有运行时间，在实际开发中应该选择效率最高的算法，这样能最大限度的减少运行时间或者占用空间，以二分查找为例，如果列表中包含10个数字，最多需要猜10次，如果列表包含40亿个数字，最多需要猜40亿次, 最多需要猜的次数与列表长度相同，这种情况称为 线性时间, 二分查找则不同。如果列表包含 100个元素, 最多要猜7次， 如果是 40亿个数字，最多需要猜 32次 就可以查到结果

大 O 表示法

大 O 表示法 是一种特殊的表示法， 指出了算法的速度有多快

算法的运行时间与不同的速度增加

假设检查一个元素需要 1毫秒。 使用简单查找时, 检查 100个元素，需要 100毫秒才能查找完毕，二使用 二分查找时， 只需要检查 7 个元素(log2100大约为7）, 因此需要 7毫秒就能查找完毕，然而实际查找的列表可能是10亿个元素，那在这种情况下两种算法各自需要多少时间呢？

计算方式

使用10亿个元素的列表进行二分查找，运行时间为 30毫秒(log21 000 000 000大约为30), 二分查找大约为简单查找的15倍，简单查找需要 30 * 15 = 450 毫秒, 这样计算正确吗？

解析

上面这种计算方式是不对的,随着元素的数量的增加,二分查找需要的额外时间并不多，而简单查找需要的额外的时间却很多，随着列表的增长，二分查找的速度比简单查找快得多，当列表为10亿个元素时，不是为 15 倍， 而是 3300万倍。在实际开发中，仅知道算法需要多长时间才能运行完毕是不够的, 还需知道运行时间如何随列表增长而增加。

大O表示法指出了算法有多快，假设列表包含了 n 个元素，简单查找需要检查每个元素，因此需要执行 n 次操作，使用大O表示法，这个运行时间为O(n)。 大O表示法并非以秒为单位的速度，大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

一些常见的 大 O 运行时间

  • O(log n)，也叫对数时间，这样的算法包括二分查找。
  • O(n)，也叫线性时间，这样的算法包括简单查找
  • O(n * log n)，快速排序 一种速度较快的排序算法
  • O(n2) 选择排序 一种速度较慢的排序算法
  • O(n!) 旅行商问题的解决方案 一种非常慢的算法