二分查找是个啥啊

打了两次力扣的周赛，都败在了第三题上，而且都是二分查找的题目。这下不能忍了，必须来总结一波。

# 第一次二分查找

二分查找是用来在一个有序数组中查找某一元素的算法。它的工作原理如下：

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

使用二分查找就能将原先$\Omicron(n)$时间复杂度的线性查找降低为$\Omicron(\log(n))$。但是一定要注意，二分查找一定要在有序的数组上进行。

下面放上模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int binary_search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int ret = -1;  // 未搜索到数据返回-1下标
    int mid;
    while (left <= right) {
        mid = left + ((right - left) >> 1);  // 直接平均可能会溢出，所以用这个算法
        if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid - 1;
        else {  // 最后检测相等是因为多数搜索情况不是大于就是小于
            ret = mid;
            break;
        }
    }
    return ret;  // 单一出口
}

在上面的代码中，我们每次搜索的是[left,right]这个闭区间，所以在while中要使用<=。

但是，这样的算法还是存在一些缺陷。比如对于条件nums = [1,2,2,2,3],target=2，使用上面的算法返回的下标是2。虽然答案是正确的，但我们想要得到target的左侧边界或右侧边界就不能使用上面的算法了。虽然可以先查出结果再向左或右线性搜索，但这样时间复杂度就被提高了。

# 寻找左侧边界的二分查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int left_bound(vector<int>& nums, int target) {
    if (nums.size() == 0)
        return -1;
    int left = 0;
    int right = nums.size();  // 注意

    while (left < right) {  // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;  // 注意
        }
    }
    // target 比所有数都大
    if (left == nums.size())
        return -1;
    // 未查到目标值
    return nums[left] == target ? left : -1;
}

在这里我们搜索的区间变成了左闭右开[left,right)，所以在while中使用<。

由于搜索区间变为[left,right)，所以当 nums[mid]被检测之后，下一步的搜索区间应该去掉 mid分割成两个区间，即 [left, mid)或 [mid + 1, right)。在代码中体现为left = mid + 1;和right = mid;

那么，这个模板为什么能找到左边界呢？关键在于nums[mid] == target这种情况的处理：

right = mid;

我们找到 target 时没有立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid)中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

# 寻找右侧边界的二分查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


int right_bound(vector<int>& nums, int target) {
    if (nums.size() == 0)
        return -1;
    int left = 0, right = nums.size();

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1;  // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    if (left == 0)
        return -1;
    return nums[left - 1] == target ? (left - 1) : -1;  // 注意要-1
}

由于我们对 left的更新必须是 left = mid + 1，这就导致了 while 循环结束时，nums[left]一定不等于 target了，而 nums[left-1]可能是 targe。所以我们在返回结果时要进行-1操作。

# 第二次二分查找

虽说上面的模板已经够好了，但是有些题目并不是只考一个二分，如果照着敲一遍模板还是比较费时的。这是就不得不祭出<algorithm>里的两个内置函数了：

# lower_bound

返回指向范围 [first, last) 中首个不小于（即大于或等于） value 的元素的迭代器，或若找不到这种元素则返回 last 。

仔细考虑一下，就会发现这就是上面提到的寻找左侧边界的二分查找，一下就把原来那么长的代码变成了一行，太香了。（但是上面的模板还是要掌握，有些题目是无法调库）

使用举例：

1
2
3
4
5
6


int main() {
    vector<int> nums = {1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};
    auto lower = lower_bound(nums.begin(), nums.end(), 3);
    cout << lower - nums.begin() << endl;    //3
    return 0;
}

一个小细节，lower_bound返回的是迭代器，所以lower的真实类型是vector<int>::iterator，太长了所以我们用的时候还是使用auto让编译器来补全QuQ。

# upper_bound

返回指向范围 [first, last) 中首个大于 value 的元素的迭代器，或若找不到这种元素则返回 last 。

其实就是上面寻找右侧边界的二分查找，只不过我们进行了-1操作而该函数没有而已。

使用举例：

1
2
3
4
5
6


int main() {
    vector<int> nums = {1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};
    auto upper = upper_bound(nums.begin(), nums.end(), 3);
    cout << upper - nums.begin() << endl;    //7
    return 0;
}

# 终极二分查找

上面的都是对一个数组进行二分查找，我们也可以把思路放开一点，对答案进行二分查找。我们都知道暴力法就是枚举答案然后检验枚举的值是否正确，当答案满足单调性时，我们就可以将枚举换为二分，这样能大大降低时间复杂度。

放两道例题，就是引言里我说的周赛题