二分查找算法详解与应用实例
二分查找算法在编程竞赛中具有重要地位，其核心在于通过缩小搜索范围快速定位目标值。根据查找方向不同可分为两种标准模板。
模板一（左边界查找）:
while (left < right) {
int middle = left + right >> 1;
if (validate(middle)) {
right = middle;
} else {
left = middle + 1;
}
}模板二（右边界查找）:
while (left < right) {
int middle = left + right + 1 >> 1;
if (validate(middle)) {
left = middle;
} else {
right = middle - 1;
}
}当需要寻找最小满足条件的值时采用模板一，此时中间值计算无需加一且右边界更新为mid；寻找最大满足条件值时使用模板二，此时中间值需加一且左边界更新为mid。
浮点数二分:
while (abs(right - left) > 1e-7) {
double middle = (left + right) / 2;
if (validate(middle)) {
left = middle;
} else {
right = middle;
}
}在实际应用中，二分查找通常遵循模板二获取最终结果。对于典型问题如"最小值最大化"应采用模板二，"最大值最小化"则使用模板一。
典型应用场景:
木材加工问题:
#include <iostream>
using namespace std;
const int MAXN = 1e5+10;
long long n, k, a[MAXN], res, left, right;
bool check(int val) {
long long count = 0;
for (int i=0; i= k;
}
int main() {
cin >> n >> k;
for (int i=0; i> a[i];
right = max(right, a[i]);
}
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) left = mid;
else right = mid - 1;
}
cout << left;
return 0;
} 区间素数查询:
#include <iostream>
using namespace std;
const int MAXN = 1e6+10;
int n, m, k, res, num, prime[MAXN];
bool vis[MAXN];
bool check(int len) {
int head = n-1, tail = n, cnt = 0;
while (head - tail + 1 > len) {
head++;
if (!vis[head]) cnt++;
}
while (head <= m) {
if (cnt < k) return false;
head++; if (!vis[head]) cnt++;
tail++; if (!vis[tail-1]) cnt--;
}
return true;
}
int main() {
cin >> n >> m >> k;
vis[1] = true;
for (int i=2; i<=m; i++) {
if (!vis[i]) {
prime[++num] = i;
vis[i] = i;
}
for (int j=1; prime[j]<=m/i; j++) {
vis[i*prime[j]] = true;
if (!(i%prime[j])) break;
}
}
if (!check(m-n+1)) cout << -1;
int left = 1, right = m+1;
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) right = mid;
else left = mid + 1;
}
cout << right;
return 0;
}借教室问题:
#include <iostream>
using namespace std;
const int MAXN = 1e6+10;
long long c[MAXN], need[MAXN], st[MAXN], ed[MAXN], n, m, res, a[MAXN], p[MAXN];
bool check(int days) {
memset(c, 0, sizeof(c));
for (int i=1; i<=days; i++) {
c[st[i]] += need[i];
c[ed[i]+1] -= need[i];
}
for (int i=1; i<=n; i++) {
p[i] = p[i-1] + c[i];
if (p[i] > a[i]) return false;
}
return true;
}
int main() {
cin >> n >> m;
for (int i=1; i<=n; i++) cin >> a[i];
for (int i=1; i<=m; i++) cin >> need[i] >> st[i] >> ed[i];
if (check(m)) cout << 0;
int left = 1, right = m;
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) left = mid + 1;
else right = mid;
}
cout << -1 << endl << left;
return 0;
}浮点数二分应用:
银行贷款问题:
#include <iostream>
using namespace std;
const double EPS = 1e-9;
double now, next, need, l, r, res;
bool check(double rate) {
return pow(1/(1+rate), need) >= 1 - now/next*rate;
}
int main() {
cin >> now >> next >> need;
l = 0, r = 10;
while (r - l >= EPS) {
double mid = (l + r)/2;
if (check(mid)) r = mid;
else l = mid;
}
printf("%.1lf", l*100);
return 0;
}设备分配问题:
#include <iostream>
using namespace std;
const double EPS = 1e-5;
long double res, l, r, a[MAXN], b[MAXN], n, m;
bool check(long double rate) {
long double total = rate * m, tmp = 0;
for (int i=0; i> n >> m;
for (int i=0; i> a[i] >> b[i];
}
double sum_a = 0;
for (int i=0; i EPS) {
long double mid = (l + r)/2;
if (check(mid)) l = mid;
else r = mid;
}
cout << l;
return 0;
} 