二分查找基础 - 掌握通用模板

概述

二分查找是计算机科学中最基础的算法之一。它的概念看似简单，但实现起来却陷阱重重。很多经验丰富的工程师仍然会纠结这些细节：

• right 应该初始化为 n-1 还是 n？
• 循环条件是 left < right 还是 left <= right？
• 更新时是 mid - 1 还是直接用 mid？
• 应该返回 left 还是 right？

好消息是：一旦理解了核心原理，你就能每次都推导出正确的实现，而不需要背诵多个模板。

---

核心思想：找分界点

关键洞察是：所有二分查找问题都可以归结为查找分界点：

数组:   [1] [2] [3] [5] [5] [5] [6] [7] [9]
索引:    0   1   2   3   4   5   6   7   8
                     ↑
                  分界点
       
左侧区域:  元素 < 5  →  [1, 2, 3]
右侧区域:  元素 ≥ 5  →  [5, 5, 5, 6, 7, 9]

分界点是条件首次成立的位置。二分查找通过以下方式高效地找到这个分界点：

1. 每次迭代将搜索范围减半
2. 移动 left 来排除不满足条件的元素
3. 移动 right 来包含满足条件的元素
4. 当 left > right 时，搜索范围为空，left 指向分界点

💡 核心法则：if 条件与你要查找的目标一致。如果要找”第一个 x ≥ target”，就用 if (nums[mid] >= target)。

可视化理解

初始:        [1, 2, 3, 5, 5, 5, 6, 7, 9]    target = 5
              L                       R

第1步:       [1, 2, 3, 5, 5, 5, 6, 7, 9]    mid = 4, nums[4] = 5 >= 5 ✓
              L           M           R     → 收缩右边界

第2步:       [1, 2, 3, 5, 5, 5, 6, 7, 9]    mid = 1, nums[1] = 2 < 5 ✗
              L     M     R                 → 收缩左边界

第3步:       [1, 2, 3, 5, 5, 5, 6, 7, 9]    mid = 3, nums[3] = 5 >= 5 ✓
                    L  M  R                 → 收缩右边界

第4步:       [1, 2, 3, 5, 5, 5, 6, 7, 9]    left > right, 返回 left = 3
                    L  R                    ✓ 第一个 5 在索引 3

---

查找下界（第一个 x ≥ target）

下界是第一个大于或等于目标值的元素。如果目标值不存在，这也是插入位置。

💡 工作原理

我们维护一个闭区间 [left, right]：

1. 如果 nums[mid] >= target，答案可能在 mid 或左边 → 收缩 right
2. 如果 nums[mid] < target，答案一定在右边 → 收缩 left
3. 当 left > right 时，left 指向下界

🎮 交互式可视化

观察 left 和 right 如何收敛以找到第一个 ≥ target 的元素。

💻 模板代码

JavaScriptJavaPython

Loading...

✅ 关键要点

循环结束时…	left 指向…
目标值存在	目标值的第一次出现位置
目标值不存在	目标值应该插入的位置
所有元素 < target	n（数组末尾之后）

---

查找上界（第一个 x > target）

上界是第一个严格大于目标值的元素。

💡 工作原理

与下界几乎相同，只需把 >= 改为 >：

if (nums[mid] > target)   // > 而不是 >=

这意味着等于 target 的元素会被归入左侧区域，所以我们找到的是 target 所有出现位置之后的第一个元素。

🎮 交互式可视化

注意分界点是如何跳过所有等于 target 的元素的。

💻 模板代码

JavaScriptJavaPython

Loading...

🔗 与下界的关系

upperBound(target) = lowerBound(target + 1)   // 对于整数

等于 target 的元素个数：

count = upperBound(target) - lowerBound(target)

---

查找第一次出现位置

要查找特定值的第一次出现位置，使用下界并验证：

🎮 交互式可视化

💻 模板代码

JavaScriptJavaPython

Loading...

---

查找最后一次出现位置

要查找最后一次出现位置，可以：

1. 使用上界然后减 1，或者
2. 使用互补条件 >

🎮 交互式可视化

💻 模板代码

JavaScriptJavaPython

Loading...

🔍 关于返回值的说明

对于 searchLast，我们返回 right（而不是 left），因为：

• 当查找”最后一个 x ≤ target”时，≤ target 的元素被推向左边
• right 最终指向最右边的这类元素

---

模板对比：闭区间 vs 左闭右开

二分查找有两种常见的写法。两种都是正确的，选择一种并坚持使用。

闭区间 [left, right]

方面	值
初始 right	n - 1
循环条件	left <= right
更新 right	mid - 1
循环结束时	left > right
下界返回值	left

左闭右开 [left, right)

方面	值
初始 right	n
循环条件	left < right
更新 right	mid（不需要 -1）
循环结束时	left == right
下界返回值	left 或 right

💻 左闭右开模板

JavaScriptJavaPython

Loading...

💡 建议：左闭右开区间的边界情况更少。循环结束时 left == right，所以可以返回任意一个。

📊 选择指南

场景	推荐风格
C++ STL 风格 (lower_bound/upper_bound)	左闭右开 [l, r)
直接查找目标值	闭区间 [l, r]
避免 off-by-one 混淆	左闭右开 [l, r)
查找精确匹配	闭区间 [l, r]

---

面试真题

题目一：在排序数组中查找元素的第一个和最后一个位置 (LC 34)

题目：给定一个有序数组，找出目标值的起始和结束位置。

输入:  nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

输入:  nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解法：组合 searchFirst 和 searchLast：

JavaScriptJavaPython

Loading...

复杂度：O(log n) 时间，O(1) 空间

---

题目二：搜索插入位置 (LC 35)

题目：给定有序数组和目标值，找出目标值应该插入的位置。

输入:  nums = [1,3,5,6], target = 5
输出: 2

输入:  nums = [1,3,5,6], target = 2
输出: 1

解法：这道题完全就是查找下界 — 代码一行都不用改！

function searchInsert(nums, target) {
  return lowerBound(nums, target);
}

复杂度：O(log n) 时间，O(1) 空间

---

题目三：搜索二维矩阵 (LC 74)

题目：在一个 m×n 矩阵中搜索目标值，矩阵具有以下特性：

• 每行元素从左到右升序排列
• 每行的第一个元素大于上一行的最后一个元素

矩阵:
[1,   3,  5,  7]
[10, 11, 16, 20]
[23, 30, 34, 60]

Target: 3 → true
Target: 13 → false

关键洞察：把二维矩阵当作展平的一维有序数组！

展平后: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
索引:    0  1  2  3   4   5   6   7   8   9  10  11

对于索引 mid：
  row = mid / n
  col = mid % n

JavaScriptJavaPython

Loading...

复杂度：O(log(m×n)) 时间，O(1) 空间

逐步演示

矩阵 (3×4):                    Target = 16
[1,   3,  5,  7]
[10, 11, 16, 20]
[23, 30, 34, 60]

展平视图: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
          0  1  2  3   4   5   6   7   8   9  10  11

第1步: left=0, right=11, mid=5
       row=5/4=1, col=5%4=1 → matrix[1][1] = 11 < 16
       left = 6

第2步: left=6, right=11, mid=8
       row=8/4=2, col=8%4=0 → matrix[2][0] = 23 > 16
       right = 7

第3步: left=6, right=7, mid=6
       row=6/4=1, col=6%4=2 → matrix[1][2] = 16 == 16 ✓
       返回 true

---

题目四：两数组间的距离值 (LC 1385)

题目：给定两个整数数组 arr1 和 arr2，以及一个整数 d，计算 arr1 中有多少个元素 arr1[i]，满足对于 arr2 中的所有元素 arr2[j]，都有 |arr1[i] - arr2[j]| > d。

输入:  arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
输出: 2
解释: 
  - arr1[0] = 4: |4-1|=3 > 2, |4-8|=4 > 2, |4-9|=5 > 2, |4-10|=6 > 2 ✓
  - arr1[1] = 5: |5-1|=4 > 2, |5-8|=3 > 2, |5-9|=4 > 2, |5-10|=5 > 2 ✓
  - arr1[2] = 8: |8-8|=0 ≤ 2 ✗

输入:  arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
输出: 2

核心思路转换：

条件 |arr1[i] - arr2[j]| > d 对所有 j 成立，等价于：

• 不存在 arr2[j] 使得 arr1[i] - d ≤ arr2[j] ≤ arr1[i] + d

所以问题变成：检查 arr2 中是否存在元素落在区间 [arr1[i] - d, arr1[i] + d] 内。

关键洞察：只需要一次二分查找！

1. 对 arr2 排序
2. 对于每个 arr1[i]，找到第一个 ≥ (arr1[i] - d) 的元素位置 idx
3. 检查该元素是否 ≤ (arr1[i] + d)：
   • 如果是，说明区间内有元素，该元素不计入结果
   • 如果否（或 idx 越界），说明区间内没有元素，计数 +1

为什么一次二分就够？

已排序 arr2:  [1,  8,  9,  10]
                   
区间 [2, 6]:
              ----[======]----
              1   2      6  8 9 10
              ↑            ↑
           <左边           右边>
              
第一个 >= 2 的元素是 8
8 > 6，所以区间内没有元素 ✓


区间 [6, 10]:
              ----------[======]
              1         6  8 9 10
                           ↑
                      第一个 >= 6
              
第一个 >= 6 的元素是 8
8 <= 10，所以区间内有元素 ✗

因为数组已排序，找到第一个可能的候选元素后：

• 如果它在区间内 → 区间有元素
• 如果它在区间右侧 → 后面的元素更大，区间无元素
• 如果不存在 → 所有元素都在区间左侧，区间无元素

JavaScriptJavaPython

Loading...

复杂度：O(n log n + m log n) 时间（排序 + m 次二分），O(1) 空间（不计排序）

逐步演示

arr1 = [4, 5, 8], arr2 = [10, 9, 1, 8], d = 2
排序后 arr2 = [1, 8, 9, 10]

处理 arr1[0] = 4:
  区间 [4-2, 4+2] = [2, 6]
  idx = lowerBound(arr2, 2) = 1 (arr2[1] = 8)
  arr2[1] = 8 > 6 → 区间内没有元素 ✓
  result = 1

处理 arr1[1] = 5:
  区间 [5-2, 5+2] = [3, 7]
  idx = lowerBound(arr2, 3) = 1 (arr2[1] = 8)
  arr2[1] = 8 > 7 → 区间内没有元素 ✓
  result = 2

处理 arr1[2] = 8:
  区间 [8-2, 8+2] = [6, 10]
  idx = lowerBound(arr2, 6) = 1 (arr2[1] = 8)
  arr2[1] = 8 ≤ 10 → 区间内有元素 ✗
  result = 2 (不变)

最终返回 2

---

常见陷阱

1. 整数溢出

❌ 错误写法：

const mid = (left + right) / 2;  // 可能溢出！

✅ 正确写法：

const mid = left + Math.floor((right - left) / 2);

💡 在 Java/C++ 中，left + right 可能超过 INT_MAX。始终使用安全公式。

2. 死循环

❌ 错误写法：

if (nums[mid] >= target) {
  right = mid;  // 对于闭区间是错的！
}

使用闭区间 [left, right] 时，如果不做 mid - 1，范围可能永远不会缩小。

死循环示例：

nums = [1, 2], target = 2
left = 0, right = 1, mid = 0
nums[0] = 1 < 2, 所以 left = 1
left = 1, right = 1, mid = 1
nums[1] = 2 >= 2, right = mid = 1  // 卡住了! left <= right 永远成立

3. 边界检查的 Off-by-One 错误

始终验证结果：

const idx = lowerBound(nums, target);
// 访问 nums[idx] 前先检查边界
if (idx < nums.length && nums[idx] === target) {
  // 找到了
}

4. 返回值错误

查找类型	返回值	原因
下界	left	右侧区域的第一个元素
上界	left	右侧区域的第一个元素
第一次出现	left（然后验证）	target 的下界
最后一次出现	right（然后验证）	上界 - 1

5. 混用模板风格

❌ 不要混用风格：

let left = 0, right = nums.length - 1;  // 闭区间风格
while (left < right) {  // 错误！这是左闭右开风格
  // ...
}

✅ 保持一致：

// 闭区间: [left, right]
let left = 0, right = nums.length - 1;
while (left <= right) {
  right = mid - 1;  // 或 left = mid + 1
}

// 左闭右开: [left, right)
let left = 0, right = nums.length;
while (left < right) {
  right = mid;  // 或 left = mid + 1
}

---

总结

🔑 通用模板

所有在有序数组中的二分查找问题都遵循这个模式：

while (left <= right) {
  const mid = left + Math.floor((right - left) / 2);
  if (/* 条件与我们要找的一致 */) {
    right = mid - 1;
  } else {
    left = mid + 1;
  }
}
return left;  // 或 right，取决于问题

📋 速查表

问题	条件	返回值
第一个 x ≥ target	nums[mid] >= target	left
第一个 x > target	nums[mid] > target	left
最后一个 x ≤ target	nums[mid] > target	right
最后一个 x < target	nums[mid] >= target	right

💡 关键要点

1. 用分界点思考：二分查找是找条件变为真的位置
2. 条件与目标匹配：if 条件应该与你要查找的目标一致
3. 选择一种风格：要么闭区间 [l,r]，要么左闭右开 [l,r)，但要保持一致
4. 验证结果：始终检查返回的索引是否有效且匹配目标

🎯 面试技巧：被问到二分查找问题时，先确定你要找的是什么”条件”，然后套用模板。练习大声解释你的思路！

📚 下一步

准备好学习更高级的二分查找了吗？查看 二分查找进阶：两段性的本质，了解二分查找如何在非有序数组上工作，如旋转数组和峰值查找！