二分查找的边界问题

前言

二分查找(Binary Search)是一种高效的查找算法，时间复杂度为O(log n)。它适用于已排序的数组或列表。本文将详细介绍二分查找的两种常见写法：闭区间写法和左闭右开区间写法。

一、二分查找基本思想

二分查找的核心思想是"分而治之"：

1. 将查找区间分成两部分
2. 比较中间元素与目标值
3. 根据比较结果决定继续在左半部分或右半部分查找
4. 重复上述过程直到找到目标值或确定目标值不存在

二、闭区间写法 [left, right]

闭区间写法中，查找区间包含左右边界，即[left, right]。

代码实现

#include <vector>
using namespace std;int binarySearchClosed(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 闭区间包含右边界while (left <= right) { // 1.注意是<=int mid = left + (right - left) / 2; // 2.防止溢出if (nums[mid] == target) {return mid; // 找到目标} else if (nums[mid] < target) {left = mid + 1; // 3.搜索右半部分} else {right = mid - 1; // 4.搜索左半部分}}return -1; // 未找到
}

关键点说明

1. 初始化：right = len(nums) - 1，因为要包含最后一个元素

2. 循环条件：left <= right，因为当left == right时区间[left, right]仍然有效

3. 边界更新：

   • left = mid + 1：因为nums[mid]已经检查过，可以排除
   • right = mid - 1：同理

三、左闭右开区间写法 [left, right)

左闭右开区间写法中，查找区间包含左边界但不包含右边界，即[left, right)。

代码实现

int binarySearchLeftClosed(vector<int>& nums, int target) {int left = 0;int right = nums.size(); // 右边界不包含while (left < right) { // 注意是<int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1; // 搜索右半部分} else {right = mid; // 注意不是mid-1}}return -1;
}

关键点说明

1. 初始化：right = len(nums)，因为右边界不包含

2. 循环条件：left < right，因为当left == right时区间[left, right)无效

3. 边界更新：

   • left = mid + 1：与闭区间相同
   • right = mid：因为右边界不包含，所以不需要mid - 1

四、两种写法的比较

特性	闭区间写法	左闭右开区间写法
初始化右边界	len(nums)-1	len(nums)
循环条件	left <= right	left < right
右边界更新	right = mid - 1	right = mid
区间含义	[left, right]	[left, right)
终止条件	left > right	left == right

五、实际应用中的选择

两种写法都是正确的，选择哪一种主要取决于个人习惯和具体场景：

1. 闭区间写法：

   • 更直观，区间定义明确
   • 边界更新对称（left=mid+1, right=mid-1）

2. 左闭右开区间写法：

   • 右边界初始化更简单（直接使用nums.size）
   • 在某些变种问题中可能更方便

六、例题展示

例题链接：704. 二分查找 - 力扣（LeetCode）

解答：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){int mid = (right - left) / 2 + left;int num = nums[mid];if (num == target) {return mid;} else if (num > target) {right = mid - 1;} else {left = mid + 1;}}return -1;}
};

七、常见错误与注意事项

1. 溢出问题：计算mid时使用left + (right - left) // 2而不是(left + right) // 2，防止left和right很大时相加溢出
2. 边界更新错误：确保在左闭右开写法中不要错误地使用right = mid - 1
3. 循环条件混淆：注意两种写法的循环条件不同
4. 未排序数组：二分查找要求输入数组必须是有序的

八、总结

二分查找是一种高效且常用的算法，掌握其两种区间写法对于解决各种变种问题非常有帮助。理解区间定义和边界更新规则是关键，建议通过大量练习来熟练掌握这两种写法。

希望这篇博客能帮助你更好地理解二分查找算法！在实际编程中，可以根据具体情况和个人偏好选择适合的写法。