二分答案选讲

约 682 字大约 2 分钟

2026-04-28

二分查找基础

首先我们先要了解如何进行二分查找，对于一个有序的数组，我们可以通过二分来查找我们需要的内容。

我个人比较喜欢左闭右开的写法，下面给出例子：

lower_bound.cc
int lower_bound(vector<int>& nums, const int& target) {
   int left = 0, right = nums.size();
   while (left < right) {
       int mid = left + (right - left) / 2;
       if (nums[mid] < target)
           left = mid + 1;
       else
           right = mid;
   }
   return left;
}

这就是容器的 std::lower_bound 的实现方式，返回第一个 $\geqslant x$ 元素的迭代器，如果值存在: 返回该值的第一个位置。如果值不存在: 返回比目标值 大的第一个元素 位置。如果所有元素都小于目标值: 返回 end() 迭代器。

那么与其相对的，std::upper_bound 返回第一个 $> x$ 指定值的元素的迭代器。如果值存在: 跳过所有相同值，返回比目标值 大的第一个元素 位置。如果值不存在: 返回比目标值 大的第一个元素 位置。如果所有元素都小于等于目标值: 返回 end() 迭代器。

虽然标准库只提供了“大于”和“大于等于”的函数，但是用这两个函数，可以组合出“小于”，“小于等于”和“等于”的判定。

samples.cc
#include <bits/stdc++.h>

int main() {
    std::vector<int> vec = {1, 2, 4, 4, 4, 6, 8, 10};
    int target = 4;

    // lower_bound
    auto lower = std::lower_bound(vec.begin(), vec.end(), target);
    std::cout << "lower_bound of " << target << " is at index: " << (lower - vec.begin()) << std::endl;

    // upper_bound
    auto upper = std::upper_bound(vec.begin(), vec.end(), target);
    std::cout << "upper_bound of " << target << " is at index: " << (upper - vec.begin()) << std::endl;

    // 找到最后一个小于 target 的元素
    if (lower != vec.begin()) {
        auto last_less = lower - 1;
        std::cout << "Last element less than " << target << " is " << *last_less << " at index " << (last_less - vec.begin()) << std::endl;
    } else {
        std::cout << "No element is less than " << target << std::endl;
    }

    // 找到最后一个小于等于 target 的元素
    if (upper != vec.begin()) {
        auto last_less_equal = upper - 1;
        std::cout << "Last element less than or equal to " << target << " is " << *last_less_equal << " at index " << (last_less_equal - vec.begin()) << std::endl;
    } else {
        std::cout << "No element is less than or equal to " << target << std::endl;
    }

    return 0;
}

简单总结就是：

函数	返回	若值存在	若值不存在	典型应用
lower_bound	第一个 >= target 的迭代器	目标值的第一个位置	第一个比它大的元素	查找元素、插入位置
upper_bound	第一个 > target 的迭代器	跳过所有相同值的元素	第一个比它大的元素	计算元素出现次数
lower_bound - 1	最后一个 < target 的迭代器	目标值前一个元素	最大的小于 target 的元素	反向查找小于目标值
upper_bound - 1	最后一个 <= target 的迭代器	目标值最后一个位置	最大的小于等于 target 的元素	反向查找小于等于目标值