跳转至

0x03 二分搜索

[toc]

1. 什么是二分搜索

通俗来说，二分搜索是在搜索的过程中，根据被搜索问题某种属性快速排除掉不可行解，找出问题可行解与不可行解的分界点的一种思想。

对于一个问题的求解，可以将其抽象为一个函数。对于一个函数的定义域，如果一部分存在某种属性，而另一半不存在，使得这两部分得以区分，并且这两部分互相不相交，存在明确的分界点。我们就可以使用二分搜索来求解出问题的分界点。

首先取定义域的最中间点，如果发现当前满足属性，那么就可以判断出问题的解，也就是分界点只可能在中间点的右边，这样就直接排除了一半的搜索量，反之亦然。

如此反复，直到找出问题的分界点。

2. 整数定义域二分

对于整数定义域的二分，一定没有明确的分界点，对于满足属性的区间（假设为左区间），不满足属性的区间（假设为右区间），分界点有两个，一个在左区间内（右边就是右区间），一个在右区间内（左边就是左区间）。

因此对于整数定义域的二分，有两种二分方法，一种是满足属性的最大值，一种是不满足属性的最小值。

例如，给定有序的一串整数序列，长度为n，求整数k在序列内的起止范围。

首先考虑起始的点。不难看出，如果我们假设一个属性为大于等于要查找的k值，那么从起始的k值开始，到序列结束，都满足这个属性，而之前的都不满足该属性。此时这个点就成为了右区间内的分界点，可以使用二分搜索找出。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int binary_search_lower(int k, int left, int right) {
    int mid;
    while (left < right) {
        // there only one element left if left == right
        mid = left + right >> 1;
        if (a[mid] >= k)    right = k;
        // a[mid] satisfies the property, 
        // so the elements bigger than mid aren't the boundary
        // (exclude mid cause it's possible that a is the boundary)
        else    left = k + 1;
        // a[mid] doesn't satisfy, 
        // so any elements include mid cann't be the boundary
    }
    return right;
}

考虑两个边界问题。

第一个。首先mid的选择上应该上取整还是下取整。边界情况为只剩下两个元素，为避免进入死循环，我们需要选择正确的取整方式。

1） 假设为[满足，满足]。我们要的边界为第一个元素，而如果上取整，将会取到第二个，进入死循环。因此需要下取整，或者可以说左取整。

2） 假设为[不满足，满足]。我们要的边界是第二个元素，如果上取整依然会死循环。同理需要下取整。

3）假设为[不满足，不满足]。即对应下一个边界问题的第三种情况，同理需要下取整，否则会超出右边界。

综上，在寻找左边界（lower bound）时，应该下取整（左取整）。

第二个。如果给定的范围内不存在所找的元素，范围是多少。

1）不存在要找的元素，但是左右区间仍存在。因为我们判别边界的条件为是否满足属性。所以即便不存在要找的元素，边界仍然存在。如边界条件为>= k，那么边界条件就会是最小的满足该属性的元素。

2）不存在左区间，即全区间都是满足属性的。那么最终结果会是0（第一个元素）。因为会一直往左寻找边界，最终触碰左边界导致循环结束。

3） 不存在右区间，即全区间都是不满足属性的。那么最终结果是右区间的下标（最后一个元素）。因为会一直向右寻找边界，最终会触碰右边界导致循环结束。

对于第二种的这三个边界情况，最终的二分结果仍在区间内，可以根据自己的需要特别判断一下最终结果来得到自己需要的答案。

寻找右边界（upper bound），其实就是反过来。判断属性为<= k，找出满足属性的最大元素。不过多赘述。只需注意边界条件同上，需要上取整。

3. 实数定义域二分

对于实数定义域的二分就显得更简单一些。因为分界点明确。

但是要注意的是，因为计算机使用二进制存储，因此在存储小数时会有不准确的情况。如果直接使用==对比两个浮点数，会得到不正确的结果。一般会设定一个epsilon，如果两个浮点数之间的差值小于这个epsilon，那么就可以认为这两个浮点数是相等的。

通常把epsilon设定为1e-6。如果保留n位小数，那么取epsilon为1e-(n+3)最为稳妥。

1
2
3
4
5
6
7
8
9
double binary_search_real (double k, double left, double right, const double eps) {
    double mid = (right + left) / 2;
    while (abs(mid - k) > eps) {
        if (mid > k)    right = mid;
        else    left = mid;
        mid = (right + left) / 2;
    }
    return mid;
}

4. 时间复杂度分析

对于二分搜索，假设问题的规模为n，即搜索的定义域大小。每次二分搜索收缩一半的定义域，最坏情况为要搜索到只剩最后一个元素。

1
2
T(n) = T(n/2) + 1
T(n) = 1 * log2 n
最后更新: May 29, 2022