30 秒速览
- 什么时候用：有序数组查找、边界定位、答案具有单调性的最优化问题
- 核心思想：每次排除一半搜索空间，找到红蓝边界
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
一、直觉建立
猜数字游戏
想象你在玩猜数字游戏：我心里想一个 1-100 的数字，你每次猜一个数，我告诉你"大了"或"小了"。
聪明的玩法是什么？每次都猜中间的数。
第一次猜 50，我说"大了" → 答案在 1-49
第二次猜 25，我说"小了" → 答案在 26-49
第三次猜 37，我说"大了" → 答案在 26-36
第四次猜 31，我说"小了" → 答案在 32-36
第五次猜 34，我说"小了" → 答案在 35-36
第六次猜 35，我说"对了！"
每次都把搜索范围砍半，100 个数最多猜 7 次（log₂100 ≈ 7）。
二分查找的本质：利用有序性，每次排除一半的可能。
为什么二分这么快？
| 数据规模 n | 暴力查找 O(n) | 二分查找 O(log n) |
|---|---|---|
| 100 | 100 次 | 7 次 |
| 10,000 | 10,000 次 | 14 次 |
| 1,000,000 | 1,000,000 次 | 20 次 |
| 10^9 | 10^9 次 | 30 次 |
当 n = 10^9 时，二分比暴力快 3000 万倍。
二、核心原理：红蓝染色法
思想
把数组想象成两种颜色：
- 蓝色：不满足条件的区域
- 红色：满足条件的区域
二分查找的目标是找到红蓝边界。
数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
目标: 找第一个 >= 6 的元素
蓝蓝蓝蓝蓝红红红红红
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
↑
边界（答案）
开区间模板（推荐）
def lower_bound(nums: list[int], target: int) -> int:
"""
找第一个 >= target 的位置
开区间 (left, right)：left 和 right 都不在搜索范围内
- left 初始化为 -1（蓝色区域的右边界）
- right 初始化为 n（红色区域的左边界）
"""
left, right = -1, len(nums) # 开区间 (left, right)
while left + 1 < right: # 区间不为空
mid = (left + right) // 2
if nums[mid] < target: # mid 是蓝色
left = mid
else: # mid 是红色
right = mid
return right # right 是第一个红色位置
为什么开区间更好？
# 传统左闭右闭写法：容易写错
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # 为什么 +1？容易搞混
else:
right = mid - 1 # 为什么 -1？容易搞混
# 开区间写法：逻辑清晰
left, right = -1, len(nums)
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid # mid 确定是蓝色，成为新的左边界
else:
right = mid # mid 确定是红色，成为新的右边界
开区间的优势：
- 不需要 +1/-1：mid 确定了颜色，直接成为边界
- 返回值清晰：
right是第一个红色，left是最后一个蓝色 - 不易死循环：
left + 1 < right保证每轮都在缩小
四种二分变体统一处理
| 问题 | 蓝色条件 | 返回值 |
|---|---|---|
| >= target 的第一个 | x < target | right |
| > target 的第一个 | x <= target | right |
| <= target 的最后一个 | x <= target | left |
| < target 的最后一个 | x < target | left |
关键理解：
right是第一个红色位置（第一个满足条件的）left是最后一个蓝色位置（最后一个不满足条件的）
三、典型例题
例题 1：LC 704. 二分查找
题目：给定一个 n 个元素有序的数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果存在返回下标，否则返回 -1。
示例：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
思路
标准二分查找。用 lower_bound 找第一个 >= target 的位置，然后检查是否等于 target。
代码
def search(nums: list[int], target: int) -> int:
# 找第一个 >= target 的位置
left, right = -1, len(nums)
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid
else:
right = mid
# 检查 right 位置是否等于 target
if right < len(nums) and nums[right] == target:
return right
return -1
复杂度：时间 O(log n)，空间 O(1)
例题 2：LC 34. 在排序数组中查找元素的第一个和最后一个位置
题目：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果不存在返回 [-1, -1]。
示例：
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
思路
这道题需要找两个边界：
- 左边界：第一个 >= target 的位置
- 右边界：最后一个 <= target 的位置 = 第一个 >= target+1 的位置 - 1
代码
def searchRange(nums: list[int], target: int) -> list[int]:
def lower_bound(nums, target):
"""找第一个 >= target 的位置"""
left, right = -1, len(nums)
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid
else:
right = mid
return right
# 找第一个 >= target 的位置
start = lower_bound(nums, target)
# 检查是否存在
if start == len(nums) or nums[start] != target:
return [-1, -1]
# 找第一个 >= target+1 的位置，减 1 就是最后一个 target
end = lower_bound(nums, target + 1) - 1
return [start, end]
图解
nums = [5, 7, 7, 8, 8, 10], target = 8
找 lower_bound(8)：
蓝蓝蓝红红红
[5, 7, 7, 8, 8, 10]
↑
start = 3
找 lower_bound(9)：
蓝蓝蓝蓝蓝红
[5, 7, 7, 8, 8, 10]
↑
pos = 5, end = 5 - 1 = 4
结果: [3, 4]
复杂度：时间 O(log n)，空间 O(1)
例题 3：LC 69. x 的平方根
题目：给你一个非负整数 x，计算并返回 x 的算术平方根。结果只保留整数部分。
示例：
输入: x = 8
输出: 2 （因为 √8 = 2.8284...，取整数部分）
思路
二分答案：找最大的 k，使得 k² <= x。
对于 x = 8：
k = 1: 1² = 1 <= 8 ✓
k = 2: 2² = 4 <= 8 ✓
k = 3: 3² = 9 > 8 ✗
答案是 2
代码
def mySqrt(x: int) -> int:
# 找最后一个 k² <= x 的 k
left, right = -1, x + 1
while left + 1 < right:
mid = (left + right) // 2
if mid * mid <= x: # mid 满足条件（红色）
left = mid
else: # mid 不满足条件（蓝色）
right = mid
return left # 最后一个满足条件的值
复杂度：时间 O(log x)，空间 O(1)
例题 4：LC 33. 搜索旋转排序数组
题目：整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k 上进行了旋转。给你旋转后的数组 nums 和一个整数 target，如果存在返回下标，否则返回 -1。
示例：
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
思路
旋转数组可以看成两个有序部分：
[4, 5, 6, 7, 0, 1, 2]
-------- --------
左半部分 右半部分
关键：判断 mid 在哪个部分，然后决定往哪边搜索。
代码
def search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# 判断 mid 在左半部分还是右半部分
if nums[mid] >= nums[left]: # mid 在左半部分
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # mid 在右半部分
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
图解
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
第一次: left=0, right=6, mid=3
nums[mid]=7 >= nums[left]=4 → mid 在左半部分
target=0 不在 [4,7) → left = 4
第二次: left=4, right=6, mid=5
nums[mid]=1 < nums[left]=0 → mid 在右半部分
target=0 不在 (1,2] → right = 4
第三次: left=4, right=4, mid=4
nums[mid]=0 == target → 返回 4
复杂度：时间 O(log n)，空间 O(1)
例题 5：LC 153. 寻找旋转排序数组中的最小值
题目：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后得到。找出数组中的最小元素。
示例：
输入：nums = [3,4,5,1,2]
输出：1
思路
用红蓝染色法：
[3, 4, 5, 1, 2]
观察：最小值是"旋转点"
- 最小值左边的元素都 > nums[-1]
- 最小值及右边的元素都 <= nums[-1]
红蓝染色：
蓝蓝蓝红红
[3, 4, 5, 1, 2]
↑
最小值
代码
def findMin(nums: list[int]) -> int:
left, right = -1, len(nums) - 1
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] > nums[-1]: # mid 在左半部分（蓝色）
left = mid
else: # mid 在右半部分（红色）
right = mid
return nums[right]
复杂度：时间 O(log n)，空间 O(1)
例题 6：LC 875. 爱吃香蕉的珂珂（二分答案）
题目：珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫将在 h 小时后回来。珂珂可以决定她吃香蕉的速度 k（根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。返回她可以在 h 小时内吃掉所有香蕉的最小速度 k。
示例：
输入: piles = [3,6,7,11], h = 8
输出: 4
思路
二分答案：速度越快，用时越少（单调性）。
速度范围: [1, max(piles)]
k=1: 可能需要很多小时 ✗
k=4: 刚好 8 小时 ✓
k=5: 7 小时 ✓
k=max(piles): 肯定可以 ✓
蓝蓝蓝红红红红
找第一个红色（最小的可行速度）
代码
import math
def minEatingSpeed(piles: list[int], h: int) -> int:
def canFinish(k: int) -> bool:
"""判断速度 k 能否在 h 小时内吃完"""
hours = 0
for pile in piles:
hours += math.ceil(pile / k) # 向上取整
return hours <= h
# 二分答案：找最小的可行速度
left, right = 0, max(piles)
while left + 1 < right:
mid = (left + right) // 2
if canFinish(mid):
right = mid # mid 可行，尝试更小的
else:
left = mid # mid 不可行，需要更大的
return right
复杂度：时间 O(n log m)，n 是堆数，m 是最大堆的香蕉数
四、二分答案通用模板
二分答案适用于：答案具有单调性的问题。
def binary_search_answer():
"""
适用条件：答案具有单调性
- 如果 x 满足条件，那么 x+1 也满足（求最小）
- 如果 x 不满足条件，那么 x-1 也不满足
"""
def check(x):
"""检查 x 是否满足条件"""
pass
left, right = min_answer, max_answer
while left + 1 < right:
mid = (left + right) // 2
if check(mid):
right = mid # mid 可行，尝试更小的（求最小值）
else:
left = mid
return right
二分答案的判断标准：
- 能写出一个
check(x)函数判断 x 是否可行 - 可行性具有单调性（x 可行 → x+1 也可行，或反过来）
五、常见错误与陷阱
错误 1：返回值搞错
# 错误：不知道返回 left 还是 right
return mid # ✗ mid 可能已经不是正确的位置了
# 正确：理解 left 和 right 的含义
return right # 第一个满足条件的位置（求下界）
return left # 最后一个满足条件的位置（求上界）
错误 2：循环条件不一致
# 错误：开区间用了闭区间的条件
left, right = -1, len(nums)
while left <= right: # ✗ 可能死循环或越界
# 正确：开区间用 left + 1 < right
while left + 1 < right:
错误 3：等号分支放错
# 混淆：找 >= target 还是 > target
if nums[mid] < target: # 找 >= target
left = mid
else:
right = mid
if nums[mid] <= target: # 找 > target
left = mid
else:
right = mid
错误 4：认为二分只能用于有序数组
二分的真正条件不是"数组有序"，而是"存在可二分的单调边界"。
例如：
- 旋转数组：可以划分成两个有序部分
- 二分答案：答案的可行性具有单调性
- 找峰值：利用局部单调性
六、复盘清单
触发信号
- 数组有序（或部分有序）
- 需要找边界位置（第一个/最后一个满足条件的）
- 最优化问题，答案具有单调性（二分答案）
边界条件
- 空数组
- 单元素数组
- 所有元素相同
- target 比所有元素都大/小
常见错误
- 返回值选错（left vs right）
- 循环条件和区间定义不一致
- 等号判断错误
- 二分答案时 check 函数写错
七、题目清单
基础题
| 题号 | 题目 | 难度 | 考点 |
|---|---|---|---|
| 704 | 二分查找 | Easy | 标准二分 |
| 35 | 搜索插入位置 | Easy | lower_bound |
| 34 | 查找元素的范围 | Medium | 左右边界 |
| 69 | x 的平方根 | Easy | 二分答案 |
| 367 | 有效的完全平方数 | Easy | 二分答案 |
进阶题
| 题号 | 题目 | 难度 | 考点 |
|---|---|---|---|
| 33 | 搜索旋转排序数组 | Medium | 旋转数组 |
| 81 | 搜索旋转排序数组 II | Medium | 有重复元素 |
| 153 | 寻找旋转数组最小值 | Medium | 旋转数组 |
| 154 | 寻找旋转数组最小值 II | Hard | 有重复元素 |
| 875 | 爱吃香蕉的珂珂 | Medium | 二分答案 |
| 1011 | 在 D 天内送达包裹的能力 | Medium | 二分答案 |
| 4 | 寻找两个正序数组的中位数 | Hard | 二分第 k 小 |