搜索算法基础：二分搜索及其变种
二分搜索是算法面试的“必考题”，但面试官真正想看的不是背代码，而是你是否能灵活处理左边界、右边界、旋转数组等变体。掌握一套可迁移的回答框架，就能以不变应万变。
面试问答卡片
问题1：实现二分查找，找到目标值在有序数组中的位置，不存在返回 -1。
面试官考察点： 基础编码能力、边界条件处理、循环不变量意识。
回答框架：
- 确定数组有序性（升序）
- 初始化 left=0, right=n-1，闭区间
- while(left <= right)：mid = left + (right-left)/2
- 若 nums[mid]==target 返回 mid；否则根据大小调整 left/right
- 循环结束返回 -1
简短示例回答： 用闭区间写法：左右指针包含有效索引。当 mid 等于目标直接返回；小于目标 left=mid+1，大于则 right=mid-1。结束时未找到返回 -1。注意用 mid = left + (right-left)/2 防溢出。
可能追问： 如何处理重复元素？如果数组很大内存有限怎么办？
避坑提醒： 不要用 mid = (left+right)/2，大数会溢出；while 条件与区间定义必须一致。
问题2：在有序数组中查找第一个等于目标值的位置，不存在返回 -1。
面试官考察点： 变种能力、区间收缩控制、对相等情况的处理。
回答框架：
- 采用左闭右开区间 [left, right)，初始 left=0, right=n
- while(left < right)：mid 计算同上
- 若 nums[mid] < target，left=mid+1；否则 right=mid
- 循环结束 left 指向第一个 ≥ target 的位置
- 最后校验 left 是否越界且 nums[left]==target
简短示例回答： 用左闭右开区间。相等时继续向左收缩 right=mid，最终 left 就是第一个目标位置。检查 left 是否在范围内且值等于目标，是则返回 left，否则 -1。
可能追问： 如果找最后一个等于目标的值怎么改？如果数组中全是重复值会出什么问题？
避坑提醒： 循环结束后必须校验 left 的有效性；不要用闭区间写法直接套用，否则容易死循环。
问题3：在一个旋转有序数组中搜索目标值（假设元素不重复），存在返回下标，不存在返回 -1。
面试官考察点： 局部有序判断、分情况讨论、逻辑完整性。
回答框架：
- 采用标准二分框架，每次先判断 mid 在哪一段有序子数组
- 比较 nums[mid] 与 nums[left]：若 ≥，则左半段有序；否则右半段有序
- 在有序段内看 target 是否在范围内，更新 left 或 right
- 注意处理下标循环问题
简短示例回答： 二分时先看 mid 落在哪段：如果 nums[left] ≤ nums[mid]，说明左半有序；此时若 target 在 [nums[left], nums[mid]] 之间，则 right=mid-1，否则 left=mid+1。另一侧同理，直到找到或循环结束。
可能追问： 如果元素允许重复（如 [1,0,1,1,1]）怎么办？如何优化到 O(log n)？
避坑提醒： 不能直接比较 nums[mid] 与 target 是否在一个有序段；重复场景下需退化到线性检测。
项目案例：订单金额分段统计系统
| 项目名称 | 订单金额分段统计系统 |
| 业务背景 | 电商平台运营需要快速统计不同金额区间的订单数量（如 0-100 元、100-200 元等），支持千万级历史订单。 |
| 规模指标 | 日订单量 1 亿，总订单量 50 亿，金额字段为浮点数；系统要求 p99 响应 < 10ms。 |
| 技术栈 | Java 8, 二分搜索变种（左边界 + 右边界），内存映射文件存储预排序数组。 |
| 核心难点 | 海量数据下的边界处理（大量重复金额时左边界查找可能退化）；金额数据每日增量追加，需要定期重建排序索引。 |
| 面试高频追问 | 1. 如果订单金额实时产生，如何保证二分搜索的时效性？ 2. 如何应对浮点数精度导致的查找偏差？ 3. 内存受限时如何压缩排序数组？ |
| 可迁移回答话术 | 二分搜索的前提是静态有序数据，动态场景需考虑“时间分片”或“离线重建”。遇到重复值场景时，将左边界改为右边界即可实现区间计数。面试时先分类讨论，再根据数据特点（是否重复、是否旋转）调整收缩策略。 |