快速定位目标 | 二分查找算法

日更进度：0005/1000天

提示：本文章力争使普通人群理解并使用，所以不会使用任何的专业术语。

---

简介

在实际应用中，我们经常需要再一大堆数字里面寻找一个数字，并且返回它的位置。

一个一个遍历元素吗？当然不行，如果元素数量只要几百几千个不会有什么问题。但当元素达到了千万个甚至亿个时，仅仅是遍历一遍就要很长时间，带给用户的体验自然是非常差了。

最简单的方法自然是从中间将数组劈断，然后根据目标值与中间值选择左、右边界进行查找。

但是，使用二分法查找的数组必须是单调的、有序的、有穷的。人脑在有序的数列里寻找一个数的时候采用的就是二分算法。

---

原理

背景
我们现在有一组数据，为了方便，我们用一对大括号将它们括起来。既然是“一组数据”，我们就称为数组吧。我们来看看它长什么样子：

{1,2,3,5,9,14,17,21}

为了方便表示，我们给每个数字编一个号，第一个数字是0号，第二个是一号...以此类推，并且我们可以通过一对方括号通过给数字的编号获取这个数字。

定义指针

好了，现在让我们定义两个边界指针，左边界 = 0，右边界 = 数组的长度 - 1（为什么要减去一呢？请在评论区留下你的答案）。现在边界定义完成了，而长度就是整个数组：

{1,2,3,5,9,14,17,21}
..L.......................R【1】

我们需要在这个数组里找到3，并返回它的编号。不急，我们先看一下它的中间是多少。

定义中心指针，中间 = (左边 + 右边) ÷ 2【2】，然后取整。现在大家都知道，我们的中间编号是(0 + 8) ÷ 2 = 4，也就是5这个数字。

收缩边界

因为我们的目标是“3”，所以我们先看一下中间是几，如果是3直接返回，看一下左边界是否与右边界重合，如果是直接返回边界指针。

我们需要寻找“3”，而中间是“5”，所以我们需要收缩右边界，我们先将其收缩至中心指针处，然后再往左收缩一格，现在边界数组变成了：

{1,2,3,5,9,14,17,21}
..L...R

注意：此时数组还是那个数组，只是寻找边界变了。

重新计算中心指针位置为 (2 - 0) ÷ 2 = 1，数值为2。我们要寻找3，而2比3小。这时我们收缩左边界指针到中心再往右移一格。

我们发现，这时左、右边界指针重合了，于是直接返回边界指针，查找结束。

执行过程如下：

算法源码如下：

def binary_search(alist,data):
    n = len(alist)
    first = 0
    last = n-1
    while first <= last:
        mid = (first + last) // 2
        if alist[mid] < data:
            first = mid + 1
        elif alist[mid] > data:
            last = mid - 1
        else:
            return mid
    return False

---

课后作业

写出一个计算开平方的算法

---

注解

【1】：原数组始终不变，变化的只有寻找范围。“...”没有任何意义，只是为了美观。

【2】：通常的开发中，为了避免巨大的加法造成溢出，通常写作左边界 + (右边界 - 左边界的形式)。