55、查找算法：二分查找的边界条件
二分查找，听起来简单吧？
不就是在一个有序数组里找个数嘛，每次砍掉一半，O(log n) 搞定。但说实话，我见过太多人在这个“简单”的算法上翻车了。我自己刚入行那会儿，也写过死循环的二分查找，调试到怀疑人生。
问题出在哪？
边界条件。
你想想看，left 和 right 怎么初始化？while 循环里用 left < right 还是 left <= right？mid 更新的时候要不要加 1 或减 1？
这些细节，一个不对，结果就全错了。
二分查找的两种常见写法
我个人习惯把二分查找分成两种模式：闭区间 和 左闭右开区间。这两种写法，本质上没有谁对谁错，但你必须搞清楚它们的边界规则。
1. 闭区间写法 [left, right]
这种写法最直观。左右边界都包含在查找范围内。
int binarySearch(int arr[], int n, int target) {
int left = 0;
int right = n - 1; // 闭区间，right 指向最后一个元素
while (left <= right) { // 注意：left == right 时，区间内还有一个元素
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // target 在右边，mid 已经查过了
} else {
right = mid - 1; // target 在左边，mid 已经查过了
}
}
return -1; // 没找到
}
这里的关键点：
while (left <= right)：当left == right时，区间里还有一个元素需要检查。left = mid + 1和right = mid - 1：因为mid已经比较过了，必须排除掉。
注意： 如果你写成
while (left < right)，当 left == right 时循环退出，那个唯一的元素就被漏掉了。我曾经在项目里因为这个 bug，查了整整一个下午。
2. 左闭右开写法 [left, right)
这种写法在 STL 里很常见。右边界不包含在查找范围内。
int binarySearch(int arr[], int n, int target) {
int left = 0;
int right = n; // 左闭右开，right 指向最后一个元素的下一个位置
while (left < right) { // left == right 时，区间为空
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // target 在右边，mid 已经查过了
} else {
right = mid; // target 在左边，mid 已经查过了，但 right 是开区间
}
}
return -1;
}
注意这里的区别：
while (left < right)：当left == right时，区间为空，循环结束。right = mid：因为右边界是开区间，mid已经被排除，所以right直接指向mid即可。
小技巧： 我个人习惯用左闭右开写法。因为它的循环条件
left < right 和 STL 的迭代器范围一致，不容易搞混。而且 right = mid 比 right = mid - 1 少了一次减 1 操作，心理上觉得更干净。
边界条件对比表
| 项目 | 闭区间 [left, right] | 左闭右开 [left, right) |
|---|---|---|
| right 初始值 | n - 1 | n |
| 循环条件 | left <= right | left < right |
| mid 比较后 left 更新 | left = mid + 1 | left = mid + 1 |
| mid 比较后 right 更新 | right = mid - 1 | right = mid |
| 循环退出时区间状态 | 区间为空 (left > right) | 区间为空 (left == right) |
二分查找的变体：找左边界和右边界
实际项目中，我们经常需要找第一个等于 target 的位置，或者最后一个等于 target 的位置。比如在有序数组 [1, 2, 2, 2, 3] 中找 2 的左边界和右边界。
这种场景下，边界条件就更讲究了。
找左边界（第一个等于 target 的位置）
int findLeftBound(int arr[], int n, int target) {
int left = 0;
int right = n; // 左闭右开
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
right = mid; // 即使相等，也要继续向左找
} else {
left = mid + 1;
}
}
// 检查是否找到
if (left < n && arr[left] == target) {
return left;
}
return -1;
}
找右边界（最后一个等于 target 的位置）
int findRightBound(int arr[], int n, int target) {
int left = 0;
int right = n; // 左闭右开
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > target) {
right = mid; // 大于 target，向左收缩
} else {
left = mid + 1; // 小于等于 target，向右收缩
}
}
// 检查是否找到
if (left > 0 && arr[left - 1] == target) {
return left - 1;
}
return -1;
}
核心思想： 找左边界时，遇到相等不返回，继续向左压缩；找右边界时，遇到相等不返回，继续向右压缩。最后通过检查边界值来确认是否真的找到了。
二分查找的流程图
下面这张图，把二分查找的核心逻辑画出来了。你对照着看，边界条件一目了然。
避坑指南
我总结了几条实战中容易踩的坑，你写代码的时候多留个心眼。
- 死循环： 最常见的问题。比如闭区间写法里，如果
left = mid而不是left = mid + 1，当left和right相邻时，mid永远等于left，循环就出不去了。 - 整数溢出： 计算
mid时，别用(left + right) / 2。当left和right都很大时，加起来可能溢出。用left + (right - left) / 2更安全。 - 边界检查： 找左边界或右边界时，循环结束后一定要检查
left是否越界，以及arr[left]是否真的等于target。我曾经在项目里忘了这一步，结果返回了一个错误的位置，导致后续数据全部错位。
我的习惯： 每次写二分查找，我都会在纸上把
left、right、mid 的变化过程画一遍，尤其是边界情况（比如数组只有一个元素，或者 target 在两端）。画完再写代码，基本不会出错。
二分查找的边界条件，说白了就是一套规则。你只要记住：区间定义决定了一切。闭区间就老老实实 left <= right，左闭右开就坚持 left < right。别混着用，别偷懒。
嗯，就这些。下次写二分查找的时候，多想想边界，别让一个简单的算法坑了你。
公众号:蓝海资料掘金营，微信deep3321