二分查找变体
01 / 一句话本质
在有序序列上,每一步都把范围对半切—— 你在 mid 处检查的那个谓词,决定了你找到的是哪种边界: 任意一个匹配、第一个,还是最后一个。
题目在有序数组中查找目标值输入[1, 3, 3, 5, 7, 7, 7, 9, 11]target11模式exact
10
31
32
53
74
75
76
97
118
有序输入,目标值 11。lo 置于 0,hi 置于 n−1 —— 闭区间 [lo, hi]。
步
0 / 8
lo · mid · hi
—
区间长度
—
结果
—
0 / 8
02 / 模式骨架
# 精确匹配 —— 闭区间 [lo, hi]lo ← 0; hi ← n − 1while lo ≤ hi:mid ← lo + (hi − lo) / 2 // 避免溢出if arr[mid] = target: return midif arr[mid] < target: lo ← mid + 1else: hi ← mid − 1# 最左侧 —— 半开区间 [lo, hi);把严格小于改成非严格小于# 最右侧 —— 半开区间 [lo, hi);用 arr[mid] ≤ target,返回 lo − 1
03 / 什么时候用这个模式
"有序"
输入有序,或可以变换成行为等价于有序的形式。 正是有序性让"丢弃一半"这一步合法。
"O(log n)"
预期复杂度暗示着对半 —— 多数别的工具都达不到对数时间。
"首次 / 末次出现"
你要找的是边界,而不是随便一个匹配 —— 就该用 最左 / 最右(lower_bound / upper_bound)。
"对答案二分"
答案是一个数,你可以判断"这个值是否满足某个谓词"。 合法答案集合关于这个值是单调的 —— 那就对值二分,而不是对下标二分。
04 / 常见坑
i.
(lo + hi) / 2 的整数溢出。对于使用定长整数的语言,数组较大时
lo + hi 可能溢出。 改用 lo + (hi − lo) / 2 —— 中点相同,但不会溢出。ii.
闭区间
[lo, hi] 与半开区间 [lo, hi) 混用。每道题选定一种约定就别变。循环条件(
≤ 还是 <) 与边界更新方式(mid − 1 还是 mid)必须一致, 否则要么差一,要么死循环。iii.
区间不收缩的死循环。
如果某个分支下
lo 和 hi 可能保持不变,循环就停不下来。 每个分支必须严格缩小区间 —— 在 lo = hi 这个边界场景下,在纸上手验一遍。05 / 去 LeetCode 上练习
四道题,按难度排序。前两道是基础二分;第三道是最左/最右变体;第四道把你引向"对答案二分"的思路。