左闭右开二分查找：一套模板搞定所有场景

左闭右开二分查找：一套模板搞定所有场景

二分查找是算法面试和工程开发中的高频考点，但左闭右闭、左闭右开两种写法容易混淆出错。

今天给大家整理一套彻底统一、零歧义、永不死循环的左闭右开二分模板，背会这一套，所有二分查找问题直接套用，堪称标准答案！

一、核心基础：左闭右开定义

这是理解整个模板的前提，必须牢牢记住：

1. 区间规则

1
[l, r)
  • 左闭：l 是有效下标，可以取到
  • 右开：r 是边界下标，永远取不到

2. 初始化写法

1
2
int l = 0;        // 左边界：数组起始位置
int r = nums.length;  // 右边界：数组长度（取不到最后一个元素）

二、万能通用模板（背诵版）

所有二分查找的核心骨架，直接背！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 初始化：左闭右开 [0, nums.length)
int l = 0, r = nums.length;

while (l < r) {
    // 防溢出写法，替代 (l+r)/2
    int mid = l + (r - l) / 2;
    
    // 核心条件：根据需求修改
    if (判断条件) {
        l = mid + 1;
    } else {
        r = mid;
    }
}

// 最终答案：一定返回 l（l == r）
return l;

三、模板核心逻辑：找「左边界」

这套左闭右开模板的本质：

查找第一个满足条件的元素位置（左边界）

最经典场景：查找第一个大于等于 target 的位置

1
2
3
4
5
6
7
8
9
10
11
// lower_bound：第一个 >= target 的位置
int l = 0, r = nums.length;
while (l < r) {
    int mid = l + (r - l) / 2;
    if (nums[mid] < target) {
        l = mid + 1;
    } else {
        r = mid;
    }
}
return l;

四、全场景对照表（重点！）

只需要修改判断条件，就能适配所有二分需求，直接查表使用：

查找目标 判断条件 区间收缩规则 返回值
第一个 ≥ target（左边界） nums[mid] < target l=mid+1 / r=mid l
第一个 > target nums[mid] <= target l=mid+1 / r=mid l
最后一个 ≤ target 转换：upper_bound - 1 同上 l - 1
最后一个 < target 转换：lower_bound - 1 同上 l - 1

关键总结：判断条件为 nums[mid] < target则l为第一个大于target的值，判断条件为 nums[mid] <= target则l为第一个大于target的值

五、关键理解：为什么只返回 l？

很多人纠结这个点，其实一句话就能懂：

  1. 循环条件是 while (l < r)
  2. 循环结束时，一定满足 l == r
  3. 整个区间收缩成了唯一的一个点，这个点就是答案

所以：

  • 返回 l 和 r 效果完全一样
  • 统一习惯返回 l 即可

六、左闭右开核心思想：保留可能解

这是左闭右开最不容易写错的关键：

r 永远是「可能答案」的上界，且不能丢弃候选值

所以代码中一定是：

1
r = mid;  // 绝对不要写 r = mid - 1

原因：

  • mid 有可能就是最终答案
  • 必须保留这个候选值，不能直接排除

七、高频两个模板：lower_bound /upper_bound

面试和刷题最常用的两个标准实现，直接复制用：

1. lower_bound（第一个 ≥ target）

1
2
3
4
5
6
7
8
9
10
11
12
public int lowerBound(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

2. upper_bound（第一个 > target）

1
2
3
4
5
6
7
8
9
10
11
12
public int upperBound(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] <= target) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

八、左闭右开 VS 左闭右闭（核心区别）

写法 区间 循环条件 返回值
左闭右闭 [l, r] l <= r 需分情况判断
左闭右开 ✅ [l, r) l < r 永远返回 l

✅ 结论：

左闭右开写法更统一、逻辑更简洁、几乎不会出现死循环，这也是大厂优先推荐的原因。

九、一句话总结（面试必背）

左闭右开二分查找：通过 r = mid 保留可能解，最终区间收缩到 l == r，答案就是 l。

总结

  1. 统一用 [l, r) 左闭右开 区间，初始化 r = 数组长度
  2. 循环条件固定 l < r，永不死循环
  3. 收缩规则：满足条件 l = mid + 1，不满足 r = mid
  4. 最终答案永远返回 l
  5. 两套核心模板：lower_bound / upper_bound，覆盖所有场景

这套模板吃透，面试 / 刷题二分查找直接秒杀！