二分查找
1. 含义
二分查找(Binary Search)是一种高效的查找算法,核心是每次将查找范围减半,仅适用于已排序的数组或区间,时间复杂度为 O(log n)。
2. 操作过程
以在一个升序数组中查找一个数为例。它每次考察数组当前部分的中间元素:
- 如果中间元素刚好是要找的,结束搜索;
- 如果中间元素小于所查找的值,左侧只会更小,只需到右侧查找;
- 如果中间元素大于所查找的值,只需到左侧查找。
3. 前提
数据必须有序。
4. 基础代码示例
int bs(vector<int>& a, int n, int target) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == target) {
return mid; // 无重复目标值时
} else if (a[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}
二分答案(猜答案)
1. 做题步骤
确定题目适合二分 -> 确定答案的范围 -> 假定一个解判断是否可行。
2. 题目类型
最值问题(可能要用二分),例如最小化最大值以及最大化最小值问题(大概率用二分)。
3. 例题 1
题目描述:给定 n 棵树的高度,求一个最大的参数值 h,使他把所有树 h 以上的部分砍掉以后,能得到 m 米或者以上的木材。换句话说,如果再升高 1 米,他将得不到 M 米木材。 思路:二分树的高度 0-400000,然后在 check 函数中去判断是否可行,即算一下得到的木材是否满足 m。 参考题目:洛谷 P1873
#include<iostream>
#include<limits>
std;
{
sum = ;
n = a.();
( i = ; i < n; i++) {
(a[i] > mid) {
sum += a[i] - mid;
}
}
(sum >= m) {
;
} {
;
}
}
{
n, m;
cin >> n >> m;
;
( i = ; i < n; i++) {
cin >> h[i];
}
l = , r = , ans = ;
(l <= r) {
mid = (l + r) / ;
((mid, h, m)) {
l = mid + ;
ans = mid;
} {
r = mid - ;
}
}
cout << ans << endl;
}
{
ios::(), cin.(), cout.();
t;
cin >> t;
(t--) {
();
}
;
}

