算法趣解之二分查找

在正式开始之前，我们先尝试来玩一个猜数游戏。游戏规则如下：

游戏裁判会指定一个从小到大的数字范围，并从中抽取一个作为猜数的正确结果。参与游戏者在分隔的状态下开始猜数。他们的每一次猜数，游戏裁判会分别告知其所猜之数是大了还是小了。最终猜数次数少者获胜。

为了获胜你会采取什么样的猜数策略呢？

第一种，随缘猜数。在脑中随便想一个数，猜中了都是缘分。

第二种，顺序猜数。从第一个数开始，一个数一个数地尝试，直到猜到最终结果。

第三种，折半猜数。每次猜数，都从数据范围的中间开始猜，依据裁判给出的反馈，丢掉不满足要求的一半。剩下的范围便作为下次猜数的参考。

我想，你看了这三种方法，应该会觉得第三种方法相较于另外两种算法靠谱一点，会选择第三种猜数策略。

拥有这种感觉，这非常棒！但是，个人感觉这种东西有时候不太好描述和形容，同时在与他人交流时也没有说服力。那么有什么好的方法来明确这种感受和并且证明你这种正确的感受呢？

让我们回到游戏本身，再此仔细阅读一下游戏规则：

游戏裁判会指定一个从小到大的数字范围，并从中抽取一个作为猜数的正确结果。参与游戏者在分隔的状态下开始猜数。他们的每一次猜数，游戏裁判会分别告知其所猜之数是大了还是小了。最终猜数次数少者获胜。

你会注意到，游戏本身已经给出来了评价的具体方式，这便是对比每一个人的猜数次数。

我们依照这种标准对三种策略来分析一下。

第一种，欧皇方式的猜数，含有大量的随机因素，猜数的次数不稳定。（这样猜数一点都不靠谱！）

第二种，如果正确答案是给定范围的第一个数，那么猜数次数只需一次；但如果正确答案是最后一个数，那么要遍历整个数据范围，才能猜到正确的数。平均下来，也要猜数次数也需要数据范围的一半的数据个数。（这多累啊···）

第三种，如果正确答案是给定范围的中间的数，那么很幸运，只需一次便可；如果正确答案是第一个或是最后一个数，那可能就会就会需要很多次。这里的很多次究竟是几次呢？这里我们一起研究一个具体的例子，来找找规律。

比如有一组数为从 1 开始，一直到 10 的 10 个整数，假定猜数的正确答案是 1 ，我们利用折半猜数的策略来分析一下：

第一次猜数，猜 5 ，

答案大了，数据范围切掉一半，剩下 1 ~ 4 ；

第二次猜数，猜 2，

答案大了，数据切掉一半，只剩下 1 ；

第三次猜数，猜 1 ，

答案正确，游戏结束。

如果将正确答案换作 10 ，上述过程又会怎样？推荐大家自己动手尝试一下，这里我不再讨论。在这种情况下，猜数次数为 4 次。

上述分析，我们很容易看到，10 个数据中猜一个数最多需要 3 ~ 4 次。这 3 和 4 究竟和 10 有什么关系呢？如果对数字敏感的同学一定会发现：log2(10) 约为 3.32 ，而这个数在 3 和 4 之间！

恭喜！这个发现是正确的！

这样想究竟有没有它的道理呢？在这里，不妨回顾一下log函数的含义。不用担心，这里不会提及太多数学上枯燥的定义，还请你耐心的看下去。结合本篇中的猜数游戏，我分享一下我对log的理解。

log2(10) 约为 3.32 ，也就是说连续的 2 相乘，需要 3.32 次，才能得到 10（前 3 个 2 相乘得到 8 ，最后一次相乘并不是乘的 2，而是比 2 小一点的数）。那么结合我们的猜数策略，每次折半猜数，以 2 为底数的 log 函数的含义便是将数据范围每次截取一半（截取到只剩一个数为止），最多能截取的次数。（脱离这个问题本身，我也推荐大家以此为引子，思考如果是以 3 为底数，log 函数又是什么意思。 4 、 5 或是其他数作为底数是否会呈现类似的规律。欢迎大家在公众号主页给我留言、和我一起探讨）

让我们再次回到之前对第三种猜数策略的分析，假设数据量为 N ，那么最多的猜数次数为 log2(N) 。结合只需猜 1 次就猜中的最好的情况，平均的猜数次数为 (1+ log2(N))/2 。

经过对三种情况的分析，仔细的你会发现，分析的时候，都会考虑到猜数次数的最好情况、最坏情况和平均情况，这对于一个思维策略来说是一个全方位的评价，他们之间的优劣也显而易见了。

其实，这样的表述还存在一点小瑕疵，就是书写不简洁。因而，那些追求简洁的理论家提出了“大O理论”来简化这里的书写。比如之前的顺序猜数，其简化写法为 O（N）；折半猜数，其简化写法为 O(log N) 。细心观察，你会发现，这里的“大O”都是在描述最坏情况下的次数，而且不计较一些常数（为什么常数会被丢弃？因为当数据量十分巨大时，这些常数对原式的影响非常少）。此外，还要注意一点，这里的“大O”只在讨论处理时间（我们称之为“时间复杂度”），用于存储数据的空间也可以类似的讨论（“空间复杂度”了解一下？）。

在这个具体的游戏中，我们一起探索并且找到了比较优异策略。这种策略能否迁移运用到其他方面？这就需要一点抽象的思维方式。迁移运用的第一步，需要我们找到各个问题的相同点，抽象出策略运用的问题场景。第二步，就是将解决问题的策略分解为一步一步切实可行的流程步骤（算法就是一系列为了完成某一任务的步骤序列），并通过某种形式表达（比如将它写成程序，从而让机器借人的智慧自动的处理某一具体问题）。

比如，本篇提到的游戏，就可以抽象为一个给定一个数据序列和待搜索的对象，进行查找的问题。在策略到流程步骤的转化中，我们就需要考虑如何存储数据、如何用三种基本的程序结构（顺序、分支、循环）去描述该策略。在查找问题中，可以利用数组存储数据，折半查找策略则可以利用循环、分支在不同的情况，对数组下标进行处理，从而完成对该策略的描述。

说了这么多，终于到了代码实现的环节。这里的代码实现，我遵循原书中的Python实现（因为这真的是一个非常简单易学的语言，并且十分适合算法的表达）。

具体代码如下（Python3.6.1测试通过）：

def binary_search(list, item):
    """
    二分查找：
      在一个从小到大排序的数据列表list中，
      搜索是否存在数据item

    参数：
      list： 保存从小到大排序的数字列表
      item： 待查找的数字
    返回：
      如果list中存在item，
      那么返回item在list中的下标，
      否则返回None
    """
    # 列表的开始的下标
    low = 0
    # 计算列表最后一个元素的下标
    high = len(list) -1
    
    while low <= high:
        # 计算介于low和high范围中间元素的下标
        mid = (int)((low + high)/2)
        #取列表中间的元素
        guess = list[mid]

        # 以下依据不同情况对下标进行处理
        if guess == item:
            return mid
        elif guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

# 测试例程
lst = [1,2,3,4,5,6,7,8,9,10]
print(binary_search(lst,1))
# 输出：0

在文章的最后，我们简单回顾一下本篇文章的要点。

算法是一系列为了完成某一任务的步骤序列
对比算法的优劣可以从最好情况、最坏情况、平均情况三个方面入手
大O可以简洁地描述算法的时间性能和存储数据的空间占用（分别称为算法的“时间复杂度”和“空间复杂度”），并且其所描述的通常是最坏情况
二分查找算法可以很快的从一个有序的序列中，查找到待查找的元素。其时间复杂度为 O (log N )。而顺序查找却要慢很多，其时间复杂度为为 O( N )。
科学探索的一种方式：从一个简单的具体问题入手，探索发现它的规律，并尝试验证这些规律的正确性。随后，考虑将具体问题和它对应的规律（或者解决方案）抽象推广，最终获得一个具有一般意义的规律（或是解决方案）。