二分查找
在有序数组中通过折半缩小区间定位目标元素，时间复杂度 。
基本实现
- 双闭区间
[left, right]：while left <= right，right = mid - 1 - 左闭右开
[left, right)：while left < right，right = mid - 中间位置：
mid = left + (right - left) // 2（防(left+right)溢出）
变体
| 场景 | 查找目标 | 核心调整 |
|---|---|---|
| 查找左边界 | 第一个 ≥ target 的位置 | 找到 target 后收紧 right |
| 查找右边界 | 最后一个 ≤ target 的位置 | 找到 target 后收紧 left |
| 查找插入点 | target 应插入的位置 | 等价于查找左边界 |
前提条件
- 数据必须有序
- 支持随机访问（数组可用，链表不适用）
- 适用于静态或低频更新的数据集