高 进阶
二分查找变体#
一句话答案#
二分不只精确查找，还能找第一个/最后一个满足条件的位置、旋转数组搜索、峰值查找等。
核心要点
常见变体：
| 变体 | 关键调整 |
|---|---|
| 第一个 ≥ target | 找到时 hi=mid-1 继续 |
| 最后一个 ≤ target | 找到时 lo=mid+1 继续 |
| 旋转数组搜索 | 判断哪半有序再选方向 |
高频题： LC33 旋转数组搜索 / LC34 查找首尾位置 / LC162 峰值
面试回答（2分钟版）
二分查找的核心不是精确查找某个值，而是每次排除一半的搜索空间。除了基础的精确查找，面试中常见几种变体。第一种是找第一个大于等于target的位置，找到了不能直接返回，要记录答案然后继续往左搜索hi=mid-1看有没有更小的；第二种是找最后一个小于等于target的，找到了继续往右搜索lo=mid+1。第三种是旋转数组搜索，关键是先判断哪一半是有序的：如果nums[lo]<=nums[mid]说明左半有序，再看target是否落在左半范围内决定搜索方向，否则右半有序做类似判断。二分最容易出错的地方是循环条件和边界更新的配套：用lo<=hi对应的是闭区间[lo,hi]，用lo<hi对应的是左闭右开[lo,hi)，两者的更新逻辑不同不能混用。我的经验是统一用闭区间写法lo<=hi配合lo=mid+1和hi=mid-1比较不容易出错。浮点数二分则不需要考虑边界整除问题，直接用精度eps控制循环终止条件。
追问与易错
追问方向：
- “二分查找的边界条件怎么处理？”→ 明确搜索区间是闭区间 [l,r] 还是左闭右开 [l,r)，统一写法避免混乱；循环条件、mid 计算、边界更新三者必须配套一致
- “旋转数组有重复元素怎么办？”→ 当 nums[mid]==nums[right] 时无法判断哪半边有序，只能 right— 线性缩小范围；最坏时间退化为 O(n)，如 [1,1,1,0,1]
- “浮点数二分怎么做？”→ 将 while 条件改为 right-left > eps（如 1e-6），不再用整数下标；每次取 mid=(left+right)/2 不需要防溢出，循环约 log2(范围/精度) 次收敛
易错点：
- ❌ 二分只能用于有序数组——旋转/峰值等场景也可以
- ❌ while 条件用 < 还是 <= 搞不清——取决于搜索区间定义