---
url: /algo/xt6daahp/index.md
---
## 二分查找基础

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

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

```cpp title="lower_bound.cc" :collapsed-lines
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()` 迭代器。

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

```cpp title="samples.cc" :collapsed-lines
#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 的元素 | 反向查找小于等于目标值 |