【萌新也能看懂的算法入门指南(3)】——二分搜索

1.二分搜索算法简介

在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）[1]、对数搜索算法（英语：logarithmic search algorithm）[2]，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。（摘自维基百科）

二分算法的最坏时间复杂度是 $\Theta(logn)$ 的，空间复杂度是 $\Theta(1)$ 。其应用范围广泛，如分块算法中就应用了二分算法的思想，还有二叉搜索树和B+树等等。

2. 二分搜索算法思想

二分搜索算法在大部分情况下只对有单调性的问题有效（如元素有序等等），每次取中点元素进行判断：

如果中点元素值等于目标值，则直接返回其在数组中的位置；
如果中点元素值小于目标值，则继续在数组的前半部分进行搜索（即[l, mid - 1]）；
如果中点元素值大于目标值，则继续在数组的后半部分进行搜索（即[mid + 1, r])；
当区间满足区间左端点小于等于右端点时，继续查找（l <= r)。

我们观察到，二分搜索算法每次排除掉至少一半的待查找数组。

3. 举例

假设我们要从数组arr = [1, 2, 3, 4, 5] 找到target = 2的位置。

首先，我们找到中点 2 ，arr[2] = 3，此时，大于目标值，所以我们将答案锁定在区间[0, 1]之间

然后，我们找到中点 0 , arr[0] = 1，此时，小于目标值，所以我们将答案锁定在区间[1, 1] 之间

此时，因为 arr[1] == 2，所以我们直接返回答案1。

4. 应用场景

给出 f(x) = y，给出 y 来求 x 是一个复杂问题，但给出 x 来求y是一个简单问题。

比如给出数组下标，求数组的值是一个简单问题，如果给出数组中的值，反推数组中的下标，是一个复杂问题。

也即使用二分算法需要满足的两个充要条件：

给出 y 求 x 是一个复杂问题
给出 x 求 y 是一个简单问题

两个条件缺一不可。当不满足2时，正反求解都是复杂问题，无法求解，当不满足1时，正反求解都是简单问题，没必要使用二分来求解。

另外，使用二分算法时，函数 f(x)需要满足单调性，但这个只是充分非必要条件，某些情况下，也能使用二分来求解。

比如，利用二分法求零点问题，只要是连续函数，根据零点定理，满足 f(a)、f(b) 异号，则区间 [a，b] 至少有一个零点。

二分法求零点的过程：

（1）确定区间[a,b]，验证f(a)f(b)<0，给定精确度ε；
（2）求区间(a,b)的中点x1；
（3）计算f(x1)；
①若f(x1) = 0，则x1就是函数的零点；
②若f(a)f(x1) < 0，则令b = x1（此时零点x∈(a, x1)); 即图象为（a,x1）
③若f(x1)f(b) < 0，则令a = x1。（此时零点x∈(x1, b)
（4）判断是否满足条件，否则重复(2)~(4)

所以二分法适用于连续函数，并不是只适用于单调函数。如果不是单调函数，函数值同号不能代表中间没有零点有可能是有2个或偶数个零点，如 $y=x^2-4$ , 当 $x=3$ 和 $x = -3$ 时 y 都大于 0，但实际上有2个零点。函数值异号一定有零点但不一定只有1个零点，有可能有奇数个零点。

5. 模型

实际上，广泛的二分算法模型实际上就是三种基本模型：

假设有一个 1 2 3 4 ... 100 101 ... 这样的数组，我们需要找到某个元素的准确位置
假设有一个 0 0 0 0 ... 1 1 1 1 ... 这样的数组，我们需要找到第一个 1 的位置
假设有一个 1 1 1 1 ... 0 0 0 0 ... 这样的数组，我们需要找到最后一个1的位置

查找某个元素的准确位置

这里的思路同小节2。

int arr[100] = {1, 2, 3, ..., 100};
int find_target(int*arr, int n, int target) {
    int l = 0, r = 100;
    while(l <= r) { // 这里带等号是因为，如果l == r时，但是此时不带等号会直接跳出循环，漏解
        int mid = (l + r) >> 1;
        if(arr[mid] == target) return mid;
        else if(arr[mid] > target) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

找到第一个1的位置

这里我们可以分成两种情况：

arr[mid] == 1 ，那么该位置有可能称为答案，所以令 r = mid
arr[mid] == 0，那么答案一定在该位置之后，所以令 l = mid + 1

// 这里实际上是100个元素，最后一个1是我们增加的哨兵元素
int arr[101] = {0, 0, 0, 0, ..., 1, 1, 1, 1... 1, 0}; 
int find_first_one(int* arr, int n) {
    int l = 0, r = n; // 二分的区间是[l, r]，本来应该是[0, n - 1]，但我们增加了哨兵元素
    while(l < r) {
        int mid = (l + r) >> 1; // 溢出问题情况下面的小节
        if(arr[mid] == 0) l = mid + 1; // 如果当前位置为 0，那么第一个1一定在这个位置之后
        else r = mid; // 否则，如果当前位置为1，那么这个位置有可能是答案
    }
    return l == n ? -1 : l;  // 如果不存在则返回-1
}

找到最后一个1的位置

这里我们实际上同样是可以看做找到第一个1的位置，我们只需要把数组中的原函数取反，即可化成上述的问题，

那么此时，我们应该是找到的第1个0的位置，所以最后需要对答案减一。

// 这里实际上是100个元素，最后一个0是我们增加的哨兵元素
int arr[101] = {1, 1, 1, 1, ..., 0, 0, 0, 0, 0};
int find_last_one(int *arr, int n) {
    int l = 0, r = n; // 二分的区间是[l, r]，本来应该是[0, n - 1]，但我们增加了哨兵元素
    while(l < r) {
        int mid = (l + r) >> 1; // 溢出问题情况下面的小节
        if(arr[mid] == 1) l = mid + 1; // 如果当前位置为 1，那么第一个0一定在这个位置之后
        else r = mid; // 否则，如果当前位置为1，那么这个位置有可能是答案
    }
    return l - 1;  // 如果l == n,说明数组中的元素全是1，所以返回 l - 1， 如果全是0，则返回-1
}