search二分搜索
二分搜索题型：怎么识别、怎么讲、怎么练
二分搜索的本质是利用单调性。真正强的候选人不会只把它理解成“有序数组里找数”，而会把它看成一个从 false 变 true 的判定过程。
覆盖题量
40+
推荐起手
先定义判定函数，再决定左右边界写法。
高频误区
区间写法不统一，导致死循环。
什么时候该想到这个模式
你能写出一个只发生一次翻转的判定函数。
题目在问第一个满足、最后一个满足、最小可行值或最大可行值。
线性扫描能做，但数据量明显在暗示你应该更快。
下手前的检查清单
先定义判定函数，再决定左右边界写法。
明确右边界是闭区间还是开区间。
一侧维护 false 区间，另一侧维护 true 区间。
返回的是边界，不是最后一个 mid。
真正适合面试表达的解题步骤
1
先用自然语言写出单调判定条件。
2
确保搜索区间一定覆盖答案。
3
mid 的作用是测试可行性，不是拍脑袋试数。
4
每次更新边界都要保证不变式仍成立。
5
最后返回代表“第一个可行”或“最后一个不可行”的边界。
常见变体
精确查找
最经典的有序数组里精确找目标值。
边界二分
查找第一个或最后一个满足条件的位置。
答案空间二分
不是在数组上二分，而是在容量、速度、答案值上二分。
模板预览
Python公开预览
# Find first position where check(mid) is true
left, right = 0, n
while left < right:
mid = left + (right - left) // 2
if check(mid):
right = mid
else:
left = mid + 1
return left
更像真实刷题路径的推荐题单
这组题不是随机罗列，而是按“先建立识别感，再补关键变体，最后上强度”去排，适合真的拿来做一轮 pattern 复习。
入门建立直觉
#69 Sqrt(x)
计算 x 的整数平方根。
你不是在数组位置上二分，而是在可行答案边界上二分。
入门建立直觉
#33 Search in Rotated Sorted Array
在旋转有序数组中查找目标值。
不是随便比较 target 和某个数，而是利用“哪一半有序”的结构来安全淘汰半边区间。
变体补齐关键状态
#34 Find First and Last Position
在有序数组中返回目标值的起始和结束位置。
左边界和右边界本质上是两种不同的判定，因此应该分成两次二分。
变体补齐关键状态
#4 Median of Two Sorted Arrays
在对数时间内求两个有序数组的中位数。
对较短数组的分割点做二分，因为较长数组的分割点会随之被唯一确定。
高频坑点
warning
区间写法不统一，导致死循环。
warning
把 mid 当答案返回，而不是边界。
warning
没先证明单调性就硬写二分。
warning
mid 和边界更新里出现溢出或 off-by-one。
练习顺序建议
1
先刷 first/last position 这类边界题。
2
再做旋转数组和峰值问题。
3
然后进入运输容量、最小速度这类答案空间二分。
4
最后再回顾精确查找，避免思维停留在数组找数。