一句话总结
二分查找每次用中点把搜索空间砍掉一半，前提是搜索空间具有单调性（有序数组，或"答案越大越容易/越难满足"的问题）。思想简单，但边界条件极易写错——号称"十个二分九个错"。
⚖️
前提：单调性
数组有序，或判定函数随答案单调变化（二分答案）。
✂️
动作：折半
比较中点与目标，每次排除一半候选，log₂n 次出结果。
🧨
难点：边界
while 条件、mid 取法、收紧方向、返回值，差一个字符就死循环。
💡
升华：二分答案
不搜数组，直接对"答案的取值范围"二分。
一、标准二分：找等于 target 的位置
1.1 过程演示
1.2 代码模板
def binary_search(nums, target):
low, high = 0, len(nums) - 1 # 闭区间 [low, high]
while low <= high: # 注意是 <=，区间非空才继续
mid = low + (high - low) // 2 # 防溢出写法（等价 (low+high)//2）
if nums[mid] == target:
return mid # 找到
elif nums[mid] < target:
low = mid + 1 # 目标在右半
else:
high = mid - 1 # 目标在左半
return -1 # 不存在
二、找边界：左边界 & 右边界（重点）
2.1 为什么标准模板不够用？
数组有重复元素时（如 [1,2,2,2,3] 找 2），标准二分只返回"某一个 2"，无法回答"第一个 2 / 最后一个 2 在哪"。而 34. 查找元素的第一个和最后一个位置、35. 搜索插入位置 这类题考的就是边界。
2.2 左边界模板（找第一个 ≥ target 的位置）
def lower_bound(nums, target):
low, high = 0, len(nums) # 注意：high 初始为 n（左闭右开区间）
while low < high: # 区间 [low, high) 非空
mid = (low + high) // 2
if nums[mid] < target: # mid 一定不是答案 → 大胆排除
low = mid + 1
else: # nums[mid] >= target → mid 可能是答案
high = mid # 保留 mid，继续向左压缩
return low # 第一个 >= target 的下标（可能 = n）
# 应用：
# 35 搜索插入位置 = lower_bound(nums, target)
# 34 第一个位置 = lower_bound(nums, target)（再检查是否等于 target）
# 找 >= x 的最小元素 = nums[lower_bound(nums, x)]
2.3 右边界模板（找最后一个 ≤ target 的位置）
def upper_bound(nums, target):
low, high = 0, len(nums)
while low < high:
mid = (low + high) // 2
if nums[mid] <= target: # mid 可能是答案 → 保留
low = mid + 1
else:
high = mid
return low - 1 # 最后一个 <= target 的下标（可能 = -1）
# 记忆口诀：
# lower_bound：< target 的都不要 → 找"第一个大于等于"
# upper_bound：<= target 的都要 → 找"第一个大于"，再减一
⚠️ 死循环经典坑：当
规则：mid 必须被排除——要么
low = high - 1 时 mid = low。如果此时执行 high = mid 没问题；但若写成 low = mid（mid 不 +1），区间永远不缩小 → 死循环。规则：mid 必须被排除——要么
low = mid + 1，要么 high = mid（mid 保留但区间仍缩小），绝不能 low = mid。
三、旋转数组二分（LeetCode 33 / 153）
3.1 核心洞察
旋转有序数组（如 [4,5,6,7,0,1,2]）整体无序，但从任意中点切开，必有一半是有序的。判断 target 是否落在有序的那一半内，即可决定往哪边二分。
3.2 代码模板
def search_rotated(nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
if nums[low] <= nums[mid]: # 左半段有序（关键判断，含等号）
if nums[low] <= target < nums[mid]:
high = mid - 1 # target 在有序的左半
else:
low = mid + 1 # 去右半
else: # 右半段有序
if nums[mid] < target <= nums[high]:
low = mid + 1 # target 在有序的右半
else:
high = mid - 1
return -1
# 153 寻找旋转排序数组中的最小值：只需判断最小值在哪一侧
def find_min(nums):
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
if nums[mid] < nums[high]: # 右半有序 → 最小值不可能在 mid 右侧
high = mid # 保留 mid 本身
else: # nums[mid] > nums[high] → 最小值在 mid 右侧
low = mid + 1
return nums[low]
四、二分答案：二分的真正威力
4.1 什么时候用二分答案？
当题目问"在满足条件的前提下，最小/最大的那个值是多少"，并且"值越大越容易满足"（或越难满足）——即可行性关于答案单调——就可以不去搜原数组，直接对答案的取值范围做二分。
💡 典型案例：410 分割数组的最大值。把数组分成 m 段，让"各段和的最大值"尽可能小。
如果允许的最大段和是
如果允许的最大段和是
maxSum：maxSum 越大，越容易满足（分得越少）。所以 maxSum 从 max(nums)（理论下界）到 sum(nums)（上界）之间，可行性单调 → 二分找最小的可行值。
4.2 通用模板
def split_array_largest_sum(nums, m):
def feasible(max_sum):
"""判断：每段和都不超过 max_sum 时，能否分成不超过 m 段"""
cnt, cur = 1, 0
for x in nums:
if cur + x > max_sum:
cnt += 1
cur = 0
if cnt > m:
return False
cur += x
return True
low, high = max(nums), sum(nums) # 答案的取值区间
while low < high:
mid = (low + high) // 2
if feasible(mid): # 可行 → 说明还能更小
high = mid # 保留 mid，向左压缩
else: # 不可行 → 必须放宽
low = mid + 1
return low
4.3 二分答案题目清单
| 题目 | 二分的"答案"是什么 | 可行判定 |
|---|---|---|
| 410 分割数组的最大值 | 各段和的最大值 | 贪心分段，看能否 ≤ m 段 |
| 875 爱吃香蕉的珂珂 | 每小时吃 k 根 | Σ⌈pile/k⌉ ≤ h 小时 |
| 1011 在 D 天内送达包裹 | 船的载重能力 | 贪心装载，看是否 ≤ D 天 |
| 278 第一个错误的版本 | 第一个出错的版本号 | isBadVersion(mid) |
| 4 两个正序数组的中位数 | 分割线的位置 | 左半最大值 ≤ 右半最小值 |
五、避坑清单与复杂度
5.1 常见错误
| 坑 | 表现 | 修复 |
|---|---|---|
| while 条件写错 | 闭区间写 < 会漏掉最后一个元素 | 闭区间 [l,r] 配 <=；开区间 [l,r) 配 <，保持一致 |
| mid 未排除 | low = mid 导致死循环 | 用 low = mid + 1（mid 已证不是答案） |
| 整数溢出 | (low+high) 超 int 上界（C/Java） | 写 low + (high-low)/2 |
| 忘记排序 | 数组无序直接二分 | 先确认单调性；必要时先 sort |
| 返回值越界 | lower_bound 返回 n 被当索引用 | 使用前检查 idx < len(nums) |
5.2 复杂度
时间复杂度：每轮排除一半 → O(log n)。二分答案时复杂度为 O(log(答案范围) × 判定代价)。
空间复杂度：迭代写法 O(1)；递归写法 O(log n) 栈空间。
空间复杂度：迭代写法 O(1)；递归写法 O(log n) 栈空间。
与双指针的关系：两者都通过"单调排除"减少搜索量。双指针靠一次排除一个元素（O(n)），二分靠一次排除一半（O(log n)）。当数组有序且只需"查找/判定"而非"枚举所有区间"时，二分永远优于线性扫描。