C++二分查找模板如何处理边界条件？

Question

在使用C++实现二分查找时，如何正确处理左右边界的开闭情况是常见难点。许多开发者对“左闭右闭”区间（即`[left, right]`）与“左闭右开”区间（即`[left, right)`）的判断条件和更新方式容易混淆，导致死循环或漏掉边界值。例如，在`[left, right]`区间中，循环条件应为`while(left <= right)`，而在`[left, right)`中则应为`while(left < right)`。同时，mid的更新方式及后续区间划分也必须对应区间的开闭状态。请结合具体代码模板说明：在不同区间定义下，如何精准控制边界更新逻辑以确保查找结果正确？

Answer 1

一、引言：二分查找的核心在于边界控制

在C++中实现高效的二分查找算法，关键在于如何正确处理左右边界的开闭情况。许多开发者在面对“左闭右闭”区间（即[left, right]）与“左闭右开”区间（即[left, right)）时，常常因循环条件和区间更新逻辑设置不当而导致死循环或漏掉目标值。

二、基本概念回顾

• 左闭右闭区间：包含左右端点的区间，如[left, right]
• 左闭右开区间：包含左端点但不包含右端点的区间，如[left, right)
• mid计算方式：通常为mid = left + (right - left) / 2;以避免整数溢出

三、两种区间的对比分析

特性	左闭右闭 [left, right]	左闭右开 [left, right)
初始条件	left = 0; right = nums.size() - 1;	left = 0; right = nums.size();
循环条件	while(left <= right)	while(left < right)
更新方式（target < nums[mid]）	right = mid - 1;	right = mid;
更新方式（target > nums[mid]）	left = mid + 1;	left = mid + 1;

四、代码模板详解

4.1 左闭右闭区间 [left, right]

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

4.2 左闭右开区间 [left, right)

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

五、流程图解析

graph TD
    A[开始] --> B{mid位置比较}
    B -->|等于target| C[返回mid]
    B -->|小于target| D[left = mid + 1]
    B -->|大于target| E[right = mid]
    D --> F{是否left < right?}
    E --> F
    F -->|是| B
    F -->|否| G[未找到，返回-1]

六、常见误区与调试建议

1. 死循环问题：若循环条件写错，例如在左闭右开区间中误用while(left <= right)，可能导致无限循环
2. 边界遗漏：若更新right = mid - 1而使用的是左闭右开区间，则可能跳过有效解
3. 初始化错误：数组索引从0开始，应确保right取值符合当前区间定义
4. Mid偏移方向：在某些变体中（如寻找第一个/最后一个匹配项），需调整mid向上或向下取整

七、进阶应用：边界查找问题

对于需要查找第一个大于等于target的位置，或最后一个小于等于target的位置等问题，可基于上述模板进行扩展。

7.1 查找第一个大于等于target的位置（左闭右开）

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

7.2 查找最后一个小于等于target的位置（左闭右闭）

int upper_bound(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 {
            right = mid - 1;
        }
    }
    return right;
}