二分查找找左/右边界时为何容易陷入死循环？

Question

二分查找求左/右边界时易陷入死循环，根本原因在于边界更新逻辑与终止条件不匹配。典型错误如：找左边界时写 `if (nums[mid] >= target) right = mid;` 却未将 `left` 更新为 `mid + 1`，或使用 `while (left <= right)` 但未确保 `mid` 参与的区间严格收缩。当 `left == right` 且 `nums[mid] == target` 时，若 `right = mid`（而非 `mid - 1`）或 `left = mid`（而非 `mid + 1`），会导致 `left` 和 `right` 在同一位置反复赋值，无法推进——循环永远卡在 `left == right == mid`。此外，整数除法向下取整（`mid = (left + right) / 2`）会加剧左边界搜索中的“停滞”风险。规避关键：① 明确循环不变量（如 `nums[left-1] < target`）；② 边界更新必须跨过已验证位置；③ 终止条件与更新策略严格对齐。这是高频面试坑点，90% 的死循环源于未区分「搜索空间收缩」与「目标判定」两个逻辑层次。

Answer 1

```html

一、现象层：死循环的典型现场还原

当实现左边界查找时，常见错误代码如下：

while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] >= target) {
        right = mid; // ❌ 错误：未排除 mid，且未更新 left
    } else {
        left = mid + 1;
    }
}

输入 [1,2,2,2,3]，target=2，执行到 left=1, right=3 时，mid=2 → nums[2]==2 → right=2；下一轮 left=1, right=2 → mid=1 → nums[1]==2 → right=1；再下一轮 left=1, right=1 → mid=1 → right=1，陷入无限循环。

二、机制层：三重不匹配导致空间停滞

死循环本质是搜索空间未严格收缩。下表揭示三类关键错配：

维度	正确范式	典型错配	后果
终止条件	while (left < right)	while (left <= right) + 不跨位更新	临界点无法退出
mid 计算	左边界用 mid = left + (right-left)/2（向下取整）	右边界仍用同一公式	右边界搜索中 mid 偏左，left=mid 导致停滞
更新语义	「right = mid - 1」表示 mid 已被判定为非解	right = mid 但未保证 mid 可被复用	同一索引反复参与判断，无信息增量

三、抽象层：循环不变量——一切逻辑的锚点

左边界搜索的核心不变量必须明确定义为：
nums[0..left-1] < target 且 nums[right+1..n-1] >= target
这意味着：
① left 是首个可能满足 nums[i] == target 的位置；
② 每次更新必须维持该断言——故当 nums[mid] >= target 时，right 应收缩至 mid（因 mid 仍可能是左边界），但必须配合 while (left < right) 防止自锁；
③ 当 nums[mid] < target，则 left = mid + 1 ——严格跨过已验证的 mid，确保不变量延续。

四、工程层：左右边界统一模板与防错设计

以下是经生产环境验证的双边界模板（含注释说明）：

// ✅ 左边界：返回最小索引 i 满足 nums[i] == target，不存在则返回 n
int leftBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size(); // [left, right) 左闭右开区间
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1; // ✅ 跨过 mid，维护 nums[left-1] < target
        } else {
            right = mid;    // ✅ mid 仍可能是左边界，但区间严格缩小
        }
    }
    return (left < nums.size() && nums[left] == target) ? left : -1;
}

// ✅ 右边界：返回最大索引 i 满足 nums[i] == target
int rightBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left + 1) / 2; // 🔺 向上取整！避免 right 滞留
        if (nums[mid] > target) {
            right = mid - 1; // ✅ 跨过 mid
        } else {
            left = mid;      // ✅ mid 仍可能是右边界
        }
    }
    return (left >= 0 && nums[left] == target) ? left : -1;
}

五、认知层：二维解耦——搜索空间收缩 vs 目标判定

90% 的死循环源于混淆两个正交职责：

• 搜索空间收缩：由循环条件和边界更新共同定义，目标是逐步缩小候选集，与具体值无关；
• 目标判定：仅在循环退出后（或单独分支）进行，决定是否命中、是否越界。

Mermaid 流程图展示正确控制流：

flowchart TD A[初始化 left, right] --> B{left < right?} B -->|Yes| C[计算 mid] C --> D{nums[mid] < target?} D -->|Yes| E[left = mid + 1
→ 空间收缩] D -->|No| F[right = mid
→ 空间收缩] E --> B F --> B B -->|No| G[返回 left 或检查 nums[left]]

```