二分查找：自定义 upper_bound、lower_bound

二分查找详细介绍可以看这篇文章，此篇文章介绍返回索引的 upper_bound 和 lower_bound 的 C++ 实现。

lower_bound 实现代码

#include <vector>int lower_bound_index(const std::vector<int>& vec, const int& target) {int left = 0;int right = vec.size(); // 注意这里是size，不是size-1while (left < right) { // 当left == right时，搜索结束int mid = left + (right - left) / 2; // 防止溢出if (vec[mid] < target) {left = mid + 1; // 搜索区间变为[mid+1, right]} else {right = mid; // 搜索区间变为[left, mid]}}return left; // 返回不小于target的第一个元素的索引
}

upper_bound 实现代码

#include <vector>int upper_bound_index(const std::vector<int>& vec, const int& target) {int left = 0;int right = vec.size(); // 注意这里是size，不是size-1while (left < right) { // 当left == right时，搜索结束int mid = left + (right - left) / 2; // 防止溢出if (vec[mid] <= target) {left = mid + 1; // 搜索区间变为[mid+1, right]} else {right = mid; // 搜索区间变为[left, mid]}}return left; // 返回大于target的第一个元素的索引
}

比较

lower_bound 和 upper_bound 的区别主要于比较条件，lower_bound 的比较条件是 vec[mid] < target 而 upper_bound 是 vec[mid] <= target，这也是它们达成不同效果的关键。