算法 - 二分查找（含左右边界版本）

Posted on

1. 题目

给定一个升序整数数组 nums 和目标值 target：

  1. 基础版：若存在 target 返回其下标，否则返回 -1。
  2. 边界版：找出 target 在数组中的起始和结束位置（存在重复时）；不存在返回 [-1, -1]。要求 O(log n)。

示例:

1
2
3
4
5
6
nums = [5,7,7,8,8,10], target = 8
基础版: 返回 3（任一 8 的下标）
边界版: 返回 [3, 4]

nums = [5,7,7,8,8,10], target = 6
返回 [-1, -1]

2. 解题思路

二分最坑的是边界与死循环。用「左闭右闭 [left, right]」这一套统一写法最省心。

2.1 基础版

1
2
3
4
5
6
7
while (left <= right) {        // 区间非空的条件
    mid = left + ((right-left) >> 1)  // 防两数相加溢出
    if (nums[mid] === target) return mid
    else if (nums[mid] < target) left = mid + 1
    else right = mid - 1
}
return -1

2.2 边界版 = 两次「找第一个 >= / 第一个 >」

关键抽象成两个函数：

  • lowerBound(target)：第一个 >= target 的下标（左边界）。
  • upperBound(target)：第一个 > target 的下标（右边界的下一位）。

则 target 的区间是 [lowerBound, upperBound - 1]；若两者相等说明 target 不存在。

核心口诀：收缩时只要 nums[mid] >= target 就 right = mid（否则 left = mid + 1），最终 left 落在第一个满足条件的位置。注意此时 while (left < right) 且 right = mid（不减一），保持「找最左」不变量。

  • 时间复杂度：O(log n)；空间 O(1)。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 基础版：精确匹配
function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1; // 左闭右闭

    while (left <= right) {
        const mid = left + ((right - left) >> 1);
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 找第一个 >= target 的下标（可能返回 nums.length）
function lowerBound(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length; // 左闭右开 [left, right)
    while (left < right) {
        const mid = left + ((right - left) >> 1);
        if (nums[mid] < target) left = mid + 1;
        else right = mid; // mid 可能是答案，保留
    }
    return left;
}

// 找第一个 > target 的下标
function upperBound(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length;
    while (left < right) {
        const mid = left + ((right - left) >> 1);
        if (nums[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left;
}

function searchRange(nums: number[], target: number): number[] {
    const lo = lowerBound(nums, target);
    // lo 越界或值不等，说明不存在
    if (lo === nums.length || nums[lo] !== target) return [-1, -1];
    return [lo, upperBound(nums, target) - 1];
}

console.log(searchRange([5, 7, 7, 8, 8, 10], 8)); // [3, 4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6)); // [-1, -1]

4. 面试延伸

  • 两套写法别混用：left<=right / right=mid-1（闭合）与 left<right / right=mid（半开）各有约定，全程保持一致，中途换风格必死循环或漏元素。
  • 旋转数组找 target（33/153）：判断哪半边有序再决定收缩方向，是二分的最高频变体。
  • 求平方根 / 二分答案：把「在答案空间里二分」讲出来（找第一个满足条件的 x），体现你懂二分的本质是单调性。
  • 溢出：JS 的 number 是双精度浮点，>>1 会把值转成 32 位整数，mid 溢出风险比 C++ 小，但写 left + (right-left)/2 仍是好习惯。
  • 记住 lowerBound === upperBound 即「target 出现次数为 0」，upperBound - lowerBound 就是频次，一行搞定计数。

难度：中等 | LeetCode 34/704 题 | 边界处理基本功