二分查找（Binary Search）
二分查找在有序搜索空间中不断排除一半候选区间，将查找复杂度降到 O(log n)。
定义
二分查找是一种在有序数组或有序搜索空间中查找目标值的算法。它每次取中点 mid，根据 nums[mid] 与目标值的大小关系，缩小左半区间或右半区间。
核心特性
| 特性 | 说明 |
|---|---|
| 前提条件 | 搜索空间有序，或答案空间具有单调性 |
| 指针模式 | 左右指针维护搜索区间 |
| 时间复杂度 | O(log n) |
| 空间复杂度 | O(1)（迭代实现） |
| 常见难点 | 区间开闭、边界收缩、重复元素处理 |
基本框架
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
与双指针的关系
二分查找可以视为 双指针 在有序数组上的典型应用：
left和right维护当前搜索区间- 每次根据
mid排除一半区间 - 指针不是一步一步移动，而是跳跃式收缩
与分治算法的关系
二分查找也体现了 分治 思想：把问题分成左右两个区间，但每次只保留一个子问题继续求解，不需要合并结果。
常见变体
| 变体 | 目标 |
|---|---|
| 查找任意目标值 | 找到一个等于 target 的位置即可 |
| 查找左边界 | 找到第一个等于 target 的位置 |
| 查找右边界 | 找到最后一个等于 target 的位置 |
| 答案二分 | 在单调答案空间中查找最小可行值或最大可行值 |
注意事项
- 明确区间定义：闭区间
[left, right]或左闭右开[left, right) - 用
left + (right - left) / 2避免整数溢出 - 边界查找时不要过早返回，要继续收缩区间
- 只有搜索空间有序或单调时才能使用二分查找
应用场景
- 有序数组查找
- 查找左右边界
- 在单调函数或答案空间中搜索
- 与左右指针结合解决有序数组问题