二分查找：原理、循环不变量与边界处理

二分查找中未找到元素时的结果分析

在二分查找算法中，如果没有找到目标元素，最终 i 的位置将会是：目标元素应该插入的位置。
具体来说：

如果目标元素比数组中所有元素都小，i 会等于 0（表示应该插入到数组最前面）
如果目标元素比数组中所有元素都大，i 会等于数组长度（表示应该插入到数组最后面）
如果目标元素的值在数组中的两个元素之间，i 会指向第一个大于目标元素的位置

代码示例展示了这三种情况：

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

在这里插入图片描述

循环不变量理解

循环不变量定义

对于二分查找而言，循环不变量如下：

在每次循环开始时，如果目标值 target 在数组中存在，则它必定在区间 [left, right] 内；如果不存在，则 target 应该插入的位置要么在 [left, right] 内，要么就是 left（即 right+1）。

循环不变量分析

初始化

初始时，left = 0，right = arr.size() - 1，搜索范围覆盖整个数组
循环不变量成立：如果 target 存在，它必在区间内；如果不存在，插入位置也必在此区间内或紧接其后

循环过程中的维护

在每次迭代中：

查找中间元素 mid = left + (right - left) / 2
比较 arr[mid] 与 target
- 若 arr[mid] == target：找到目标，返回 mid
- 若 arr[mid] < target：更新 left = mid + 1，缩小搜索区间
- 若 arr[mid] > target：更新 right = mid - 1，缩小搜索区间
每次更新后，循环不变量仍然成立

循环终止条件

循环在 left > right 时终止
此时 left = right + 1
left 指向的位置即为 target 应插入的位置

三种特殊情况分析

1. 目标元素比所有元素都小

循环中不断执行 right = mid - 1
最终 right = -1，left = 0
left 指向数组首位，正是插入位置

2. 目标元素比所有元素都大

循环中不断执行 left = mid + 1
最终 left = arr.size()，right = arr.size() - 1
left 指向数组末尾后一位，正是插入位置

3. 目标元素在两个元素之间

假设存在 i 使得 arr[i] < target < arr[i+1]
循环结束时 left = i+1，right = i
left 指向第一个大于 target 的位置，正是插入位置

二分查找中的边界处理技巧

1. 搜索区间的定义方式

二分查找有两种常见的搜索区间定义：

闭区间 [left, right]

while (left <= right) { // 使用 <= // ...if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}
}

左闭右开区间 [left, right)

while (left < right) { // 使用 <// ...if (nums[mid] < target) {left = mid + 1;} else {right = mid; // 注意这里是 mid}
}

2. 中间位置的安全计算

避免整数溢出：

// 推荐方式：
int mid = left + (right - left) / 2;// 不推荐：可能溢出
// int mid = (left + right) / 2;

3. 查找目标值的边界

查找第一个等于目标值的元素

int findFirstEqual(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1, result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {result = mid;      // 记录当前位置right = mid - 1;   // 继续向左寻找} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return result;
}

查找最后一个等于目标值的元素

int findLastEqual(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1, result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {result = mid;      // 记录当前位置left = mid + 1;    // 继续向右寻找} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return result;
}

4. 下界与上界查找

下界（第一个大于等于目标值的元素）

int lowerBound(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) {right = mid - 1;} else {left = mid + 1;}}return left;
}

上界（第一个大于目标值的元素）

int upperBound(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) {right = mid - 1;} else {left = mid + 1;}}return left;
}

5. 常见错误与边界测试

循环条件与区间定义匹配
- 闭区间 [left, right] 使用 left <= right
- 左闭右开区间 [left, right) 使用 left < right
边界更新的一致性
- 闭区间：left = mid + 1 和 right = mid - 1
- 左闭右开：left = mid + 1 和 right = mid
边界测试用例
- 空数组
- 目标值小于所有元素
- 目标值大于所有元素
- 目标值等于某些元素（包括首尾元素）
- 目标值在元素之间
- 数组只有一个元素的情况
循环终止条件理解
- 闭区间方式终止时：left = right + 1
- 左闭右开方式终止时：left = right