二分查找
算法概述
【二分查找】(Binary Search) 是一种高效的查找算法，用于在【有序数组】中查找特定元素。其核心思想是每次将查找区间一分为二，通过与中间元素比较，排除一半的搜索空间，从而大幅减少查找次数。
算法设计思路
二分查找的基本思路是：
- 确定查找区间的左右边界
- 计算区间中点，将待查找值与中点值比较
- 根据比较结果，将搜索范围缩小到左半部分或右半部分
- 重复上述步骤，直到找到目标值或确定目标值不存在
代码实现与解析
基本二分查找
// 在有序数组nums中查找目标值target，返回索引，若不存在则返回-1
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 注意这里是闭区间 [left, right]
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; // 目标不存在
}
查找第一个等于目标值的位置
// 在有序数组nums中查找第一个等于target的位置，不存在则返回-1
int findFirstEqual(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
if (nums[mid] == target) {
result = mid; // 记录当前找到的位置
}
right = mid - 1; // 继续在左侧查找
} else {
left = mid + 1;
}
}
return result;
}
查找最后一个等于目标值的位置
// 在有序数组nums中查找最后一个等于target的位置，不存在则返回-1
int findLastEqual(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
if (nums[mid] == target) {
result = mid; // 记录当前找到的位置
}
left = mid + 1; // 继续在右侧查找
} else {
right = mid - 1;
}
}
return result;
}
查找第一个大于等于目标值的位置（下界）
// 在有序数组nums中查找第一个大于等于target的位置，如果所有元素都小于target则返回nums.size()
int lowerBound(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 注意这里是开区间 [left, right)
while (left < right) { // 注意这里是 <，因为是开区间
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid; // 缩小右边界，但仍包含mid
} else {
left = mid + 1;
}
}
return left; // 返回下界
}
查找第一个大于目标值的位置（上界）
// 在有序数组nums中查找第一个大于target的位置，如果所有元素都小于等于target则返回nums.size()
int upperBound(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 开区间 [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left; // 返回上界
}
逻辑流程图解
基本二分查找流程：
初始区间: [0, n-1]
|
v
计算中点: mid = (left + right) / 2
|
v
比较nums[mid]和target
|
+----> nums[mid] == target: 返回mid
|
+----> nums[mid] < target: 搜索区间变为 [mid+1, right]
|
+----> nums[mid] > target: 搜索区间变为 [left, mid-1]
|
v
重复上述步骤直到找到target或区间为空
复杂度分析
- 时间复杂度：O(log n)，其中n是数组的长度
- 每次迭代将搜索空间减半，因此最多需要log₂n次比较
- 空间复杂度：O(1)，只需要常数级别的额外空间
常见的二分查找变形
二分查找有很多变形，主要用于解决以下问题：
- 【精确查找】：查找等于目标值的元素
- 【范围查找】：查找第一个/最后一个等于目标值的元素
- 【边界查找】：查找第一个大于等于/大于目标值的元素
- 【旋转数组查找】：在旋转有序数组中查找元素
- 【二分答案】：使用二分查找确定答案范围
典型例题分析
例题1: 搜索插入位置（LeetCode 35）
问题描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 注意是开区间 [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left; // 这里等价于下界(lower_bound)
}
};
分析：
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
- 核心思想：查找第一个大于等于target的位置，即lowerBound实现
例题2: 在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）
问题描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) return {-1, -1};
// 查找第一个等于target的位置
int first = findFirst(nums, target);
// 如果没找到，直接返回[-1, -1]
if (first == -1) return {-1, -1};
// 查找最后一个等于target的位置
int last = findLast(nums, target);
return {first, last};
}
private:
int findFirst(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
if (nums[mid] == target) {
result = mid;
}
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
int findLast(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
if (nums[mid] == target) {
result = mid;
}
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
};
分析：
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
- 核心思想：分别使用两次二分查找，找到目标值的第一个和最后一个位置
例题3: 搜索旋转排序数组（LeetCode 33）
问题描述：给你一个整数数组 nums，它原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转。找出并返回数组中的 target，如果未找到返回 -1。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
// 判断mid是在左侧递增区间还是右侧递增区间
if (nums[left] <= nums[mid]) {
// mid在左侧递增区间
if (nums[left] <= target && target < nums[mid]) {
// target在左侧递增区间内
right = mid - 1;
} else {
// target在右侧区间
left = mid + 1;
}
} else {
// mid在右侧递增区间
if (nums[mid] < target && target <= nums[right]) {
// target在右侧递增区间内
left = mid + 1;
} else {
// target在左侧区间
right = mid - 1;
}
}
}
return -1;
}
};
分析：
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
- 核心思想：分析中间点在哪个递增区间，然后判断目标值在哪个区间，缩小搜索范围
二分答案
除了在数组中查找元素外，二分查找还经常用于"二分答案"，即当问题的答案具有单调性时，可以用二分查找确定最优解。
例题4: 分割数组的最大值（LeetCode 410）
问题描述：给定一个非负整数数组 nums 和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int left = *max_element(nums.begin(), nums.end()); // 最小可能的最大值
int right = accumulate(nums.begin(), nums.end(), 0); // 最大可能的最大值
while (left < right) {
int mid = left + (right - left) / 2;
// 检查是否可以将数组分成m个子数组，使得每个子数组的和不超过mid
if (canSplit(nums, m, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private:
// 判断是否可以将数组分成m个子数组，使得每个子数组的和不超过maxSum
bool canSplit(vector<int>& nums, int m, int maxSum) {
int count = 1; // 子数组数量
int currentSum = 0; // 当前子数组的和
for (int num : nums) {
if (currentSum + num > maxSum) {
count++;
currentSum = num;
if (count > m) {
return false;
}
} else {
currentSum += num;
}
}
return true;
}
};
分析：
- 时间复杂度：O(n * log(sum))，其中n是数组长度，sum是数组元素和
- 空间复杂度：O(1)
- 核心思想：二分答案，猜测最大子数组和，然后验证是否可行
易错点与调试技巧
【区间定义】不同的区间定义（开/闭）需要不同的循环条件和更新方式
// 闭区间 [left, right] int left = 0, right = nums.size() - 1; while (left <= right) { // ... if (condition) right = mid - 1; else left = mid + 1; } // 开区间 [left, right) int left = 0, right = nums.size(); while (left < right) { // ... if (condition) right = mid; else left = mid + 1; }【中点计算】防止整数溢出
// 错误写法，可能导致整数溢出 int mid = (left + right) / 2; // 正确写法 int mid = left + (right - left) / 2;【边界条件】检查空数组和长度为1的数组
if (nums.empty()) return -1; // 检查空数组 if (nums.size() == 1) return nums[0] == target ? 0 : -1; // 检查长度为1的数组【死循环问题】在特定情况下可能陷入死循环
// 避免死循环的方法 while (left < right) { int mid = left + (right - left) / 2; if (condition) { right = mid; // 注意这里不是mid-1 } else { left = mid + 1; // 确保left一定会增加 } }
优化与扩展
浮点数二分查找
二分查找也适用于浮点数，但需要注意精度控制：
double binarySearch(function<bool(double)> condition, double left, double right, double eps) {
while (right - left > eps) {
double mid = left + (right - left) / 2.0;
if (condition(mid)) {
right = mid;
} else {
left = mid;
}
}
return left;
}
三分查找（寻找单峰函数极值）
对于单峰函数，可以使用三分查找来寻找极值：
double ternarySearch(function<double(double)> f, double left, double right, double eps) {
while (right - left > eps) {
double m1 = left + (right - left) / 3;
double m2 = right - (right - left) / 3;
double f1 = f(m1);
double f2 = f(m2);
if (f1 < f2) {
left = m1;
} else {
right = m2;
}
}
return f((left + right) / 2);
}
练习题推荐
- LeetCode 35: 搜索插入位置（基础二分查找）
- LeetCode 34: 在排序数组中查找元素的第一个和最后一个位置（查找边界）
- LeetCode 33: 搜索旋转排序数组（旋转数组二分）
- LeetCode 153: 寻找旋转排序数组中的最小值（旋转数组二分）
- LeetCode 162: 寻找峰值（二分查找变形）
- LeetCode 410: 分割数组的最大值（二分答案）
- LeetCode 1011: 在D天内送达包裹的能力（二分答案）
- POJ 1064: Cable master（二分答案）
- CodeForces 777B: Game of Credit Cards（二分+贪心）
总结
二分查找是一种高效的查找算法，特别适合在大型有序数据集上进行查询。掌握好二分查找的各种变体，对解决范围查询、边界查找以及最优化问题非常有帮助。二分算法的核心在于：
- 确定正确的区间定义和循环条件
- 正确缩小搜索区间
- 识别问题中的单调性，考虑使用"二分答案"的思想
在竞赛编程中，二分查找不仅可以用于数组搜索，还可以作为求解策略应用于更广泛的问题领域。当你遇到可以通过"猜测答案"来验证的问题时，考虑使用二分查找来加速解题过程。