ACM 选手带你玩转二分查找！

大家好呀，我是 Rocky0429。

今天来讲二分查找呀，可能臭宝们觉得二分查找光看一下“二分”俩字就已经学会了了原理。

确实，二分查找的原理非常简单，但是往往越简单的东西越不容易掌握， 不要把简单和容易画上等号 。

尤其二分查找在解决实际问题时，要慎之又慎，在细节上稍不注意，臭宝们就可以给自己颁一个“ bug 制造机”的头衔。

至于是不是真的有这么邪乎，接着往下看就知道了。

认识二分查找

二分查找，又叫 折半查找 ，洋名儿 Binary Search 。

二分查找的使用，要有一个 前提条件 ： 要查找的数必须在一个有序数组里 。在这个前提下，取中间位置数作为比较对象：

• 若要查找的值和中间数相等，则查找成功。
• 若小于中间数，则在中间位置的左半区继续查找。
• 若大于中间数，则在中间位置的右半区继续查找。

不断重复上述过程，直到查找成功或者查找区域变为 0，查找失败。

二分查找在我们的生活中随处可见，比如写好一个 100 以内的正整数，臭宝们来猜我写的是哪一个，我只回答是大了还是小了。

傻瓜做法是一个个的猜，这就不说了。二分查找的话会像下面一样（部分）：

由于是 100 以内的正整数，按照二分查找规则，第 1 次先猜 50，如果我说大了，那第 2 次就猜 25，如果我说小了，那第 2 次就猜 75，以此往复。

假设要猜的数是 1，那么过程如下：

你看只花了 7 次就能找到，是不是很快，而且这还是在最坏情况下，也就是 100 个数的二分查找最多 7 次就能知道结果。

根据二分查找的思想，1000 个数的二分查找最多只需要查找 10 次，10000 以内的数最多只需要查找 14 次，有谁不相信可以自己动手试试，如果你不怕累的话。

下面我带臭宝手把手的复现一个二分查找。

从数组 10、11，21，32，53，85，138，223，361 中，查找是否存在值 21。

利用二分思想，设定 low 和 high 表示需要查找的区间的左右下标，mid 表示需要查找区间的中间元素下标。

过程如下图所示：

通过上面的讲解和例子相信你对二分查找的认识已经足够了，下面就是来看如何实现二分查找。

二分查找常规实现

根据二分查找的思想，我们来看一下二分查找的常规实现。

def BinarySearch(arr, low, high, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) / 2
        if arr[mid] == target:
            # 找到 target
            return mid