二分查找与应用
基本概念
二分查找，又称折半查找或对数查找，是一种在有序数组中定位特定元素的高效算法。
工作原理
以在升序数组中查找目标值为例：
- 取当前区间的中间元素进行比较
- 若中间元素等于目标值则查找完成
- 若中间元素小于目标值，则只在右半区间继续查找
- 若中间元素大于目标值，则只在左半区间继续查找
时间复杂度分析
- 最优情况：O(1) - 目标值正好位于数组中间位置
- 平均和最坏情况：O(log n) - 每次都将搜索范围减半
空间复杂度分析
- 迭代实现：O(1) - 仅使用常数级额外空间
- 递归实现：O(log n) - 调用栈深度取决于数组长度
整数范围二分模板
bool check(int x) { /* 判断x是否满足条件 */ }
// 情况一：区间[l, r]划分为[l, mid]和[mid+1, r]
int binarySearch1(int l, int r)
{
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
// 情况二：区间[l, r]划分为[l, mid-1]和[mid, r]
int binarySearch2(int l, int r)
{
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
浮点数二分模板
bool check(double x) { /* 判断x是否满足条件 */ }
double floatBinarySearch(double left, double right)
{
const double precision = 1e-6;
while (right - left > precision) {
double mid = (left + right) / 2;
if (check(mid)) right = mid;
else left = mid;
}
return left;
}
二分答案典型应用
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int result;
int arr[200010];
bool checkCondition(int x)
{
int total = 0;
for(int i = 1; i <= n; i++)
{
// 根据具体问题计算满足条件的项
}
return /* 返回判断结果 */;
}
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
}
int low = /* 初始下界 */, high = /* 初始上界 */;
while(low <= high) {
int mid = (low + high) >> 1;
if(checkCondition(mid)) {
result = mid;
// 根据问题性质选择更新方向
high = mid - 1; // 或 low = mid + 1;
} else {
// 根据问题性质选择更新方向
low = mid + 1; // 或 high = mid - 1;
}
}
cout << result;
return 0;
}
