二分查找核心模板
二分查找的本质是在一个有序的搜索区间内，通过不断将区间一分为二，快速缩小查找范围，最终定位到目标值。其时间复杂度为 O(log n)，效率极高。
1.1 基本框架（两端都闭写法）
我们将使用两端都闭的搜索区间 [left, right]，这是最直观、最不容易出错的写法。
#include <vector>
using namespace std;
// 基本二分搜索：查找 target 在有序数组 nums 中的任意一个索引，不存在返回 -1
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 注意：右边界是最后一个元素的索引
while (left <= right) { // 当搜索区间不为空时继续
int mid = left + (right - left) / 2; // 防止溢出的写法
if (nums[mid] == target) {
return mid; // 找到目标，直接返回
} else if (nums[mid] < target) {
left = mid + 1; // target 在右半部分，收缩左边界
} else if (nums[mid] > target) {
right = mid - 1; // target 在左半部分，收缩右边界
}
}
return -1; // 循环结束未找到
}
关键点：
- 循环条件
left <= right：当left == right + 1时，搜索区间[right+1, right]为空，循环终止，不会漏掉元素。 - 边界更新
left = mid + 1和right = mid - 1：因为mid已经检查过，需要将其从搜索区间中排除。
1.2 三种常见场景
在竞赛中，我们更多需要寻找左侧边界（第一个满足条件的元素）或右侧边界（最后一个满足条件的元素）。下面给出统一的“两端都闭”模板。
场景一：寻找一个数（标准模板）
即上面的 binarySearch 函数。
场景二：寻找左侧边界
// 寻找左侧边界：返回第一个 >= target 的元素的索引
// 若 target 存在，则返回其最左侧索引；若不存在，则返回其应插入的位置
int leftBound(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1; // 搜索区间变为 [mid+1, right]
} else if (nums[mid] > target) {
right = mid - 1; // 搜索区间变为 [left, mid-1]
} else if (nums[mid] == target) {
right = mid - 1; // 关键：找到时也不返回，继续向左收缩右边界
}
}
// 循环结束时，left 指向第一个 >= target 的元素
// 如果 left 越界或 nums[left] != target，说明 target 不存在
if (left >= nums.size() || nums[left] != target) {
return -1;
}
return left;
}
如果画一个图，就是这样：
场景三：寻找右侧边界
// 寻找右侧边界：返回最后一个 <= target 的元素的索引
int rightBound(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
left = mid + 1; // 关键：找到时也不返回，继续向右收缩左边界
}
}
// 循环结束时，right 指向最后一个 <= target 的元素
if (right < 0 || nums[right] != target) {
return -1;
}
return right;
}
核心思想总结：
- 查找左侧边界：遇到
nums[mid] == target时，right = mid - 1，继续向左找。 - 查找右侧边界：遇到
nums[mid] == target时，left = mid + 1，继续向右找。