一次教你搞懂二分查找，算法学起来可以更直观！

前两天去公司应聘，还没等我开始自我介绍，面试官上来就要手撕代码。题目是这样的 :

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例：
输入: nums = [1,3,5,6], target = 5
输出: 2

题目虽然虽然很基础，但是要求时间复杂度为 O(log n) 。那么肯定就得用二分查找的方法去做了，下面就用漫画图解的形式带大家一起回顾一下二分查找。

二分查找

下面的示例说明了二分查找的工作原理。我随便想一个1~100的数字。

你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。
假设你从1开始依次往上猜，猜测过程会是这样。

这是简单查找，更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99，你得猜99次才能猜到！

更佳的查找方式

下面是一种更佳的猜法。从 50 开始。

小了，但排除了一半的数字！至此，你知道1～50都小了。接下来，你猜 75。

大了，那余下的数字又排除了一半！使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜 63（50和75中间的数字）。

这就是二分查找，你学习了第一种算法！每次猜测排除的数字个数如下。

不管我心里想的是哪个数字，你在 7 次之内都能猜到，因为每次猜测都将排除很多数字！

假设你要在字典中查找一个单词，而该字典包含 240 000 个单词，你认为每种查找最多需要多少步？

如果要查找的单词位于字典末尾，使用简单查找将需要 240 000 步。使用二分查找时，每次排除一半单词，直到最后只剩下一个单词。

因此，使用二分查找只需 18 步——少多了！一般而言，对于包含n个元素的列表，用二分查找最多需要 log₂n 步，而简单查找最多需要 n 步。

算法样例

下面来看看如何编写执行二分查找的Python代码。这里的代码示例使用了数组。如果你不熟悉数组，也不用担心。你只需知道，可将一系列元素存储在一系列相邻的桶（bucket），即数组中。这些桶从0开始编号：第一个桶的位置为#0，第二个桶为#1，第三个桶为#2，以此类推。

函数binary_search接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个函数将返回其位置。你将跟踪要在其中查找的数组部分——开始时为整个数组。

你每次都检查中间的元素。

如果猜的数字小了，就相应地修改low。

如果猜的数字大了，就修改high。完整的代码如下。

def binary_search(list, item):
    # low和high用于跟踪要在其中查找的列表部分
    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(log n) 的算法。
输入: nums = [1,3,5,6], target = 5
输出: 2

那么针对这道题，直接套用二分法即可，即不断用二分法逼近查找第一个大于等于target的下标。我们写出的二分查找算法就是这样的：

def searchInsert(nums, target):
    left, right = 0, len(nums)
    while (left < right):
        # 下面这样写是考虑大数情况下避免溢出
        mid = (right - left) // 2 + left
        if target <= nums[mid]:
            right = mid
        else:
            left = mid + 1
    return left

算法学习心得

相信大家通过上面这种图解的方式很轻松就能掌握二分查找的原理。这是《算法图解》中的一个例子，这是一本能够像小说一样有趣的算法入门书。

除了二分查找以外，本书还介绍了选择排序、递归、快速排序、散列表、广度优先搜索、狄克斯特拉算法、贪婪算法、动态规划、K最近邻算法等。本书所有的示例代码都是使用Python 2.7编写的。书中在列出代码时使用了等宽字体。有些代码还进行了标注，旨在突出重要的概念。

如果你是刚入门的同学，非常建议从类似这样的简单算法书开始学习，切记不要一上来就像一口吃个胖子，路还是得一步一步走。

如果你觉得这本书过于简单，还可以看一下普林斯顿算法红宝书《算法》，这本书是风靡全世界近 40 年的算法经典。很多大学都拿它当作教材，该书非常系统、全面、严谨，提供了实际代码，而且这些 Java 代码实现采用了模块化的编程风格，读者可以方便地加以改造。

除了看书以外，还应该加上实战练手。在具备一定的算法基础以后，就可以上leetcode开始刷题了。我是按照某一类别的题型，由易到难，循序渐进，以此来巩固对算法的理解，并且提高自己的编程能力。

最后再送给大家一句 Linux 的创始人 Linus Torvalds 的话，“Talk is cheap. Show me the code.”

一次教你搞懂二分查找，算法学起来可以更直观！