QLU_ACM 浅谈二分搜索技术
by StilllFantasy
二分思想为何物？
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
关键点：
- 优点：每次折半，速度较快
- 缺点：待查表必须为顺序表-->二分搜索的限制
- 复杂度：O ( log N )
什么意思？
简而言之就是，待查表必须是有序的，无序的话必须先排序，比如在数组二分搜索某个数的时候
举个栗子：
int a[10] = {1,2,3,4,5,6,7,8,9};
int search(int K)
{
for (int i = 0; i < N; i++)
if (num[i] == K)
{
return i;
}
return -1;
}
int search(int K, int L, int R)
{
int l = L;
int r = R;
while (l <= r)
{
if(l == r && num[l] != K)
return -1;
int mid = (l + r) / 2;
if (num[mid] < K)
return search(K, mid + 1, R);
else if (num[mid] > K)
return search(K, L, mid - 1);
else
return mid;
}
return -1;
}
二分不难写吧？
- 其实二分的思想还是蛮容易理解的
- 重点在于：它除了能在数组里查数用，还能干啥呢？
二分答案！
- 特点：速度快、神奇
注意：
- 答案满足单调性
- 预估答案区间 minAns ~ maxAns
步骤：
找区间-->取中间判断是不是答案-->折半直到找到答案
关于此类题目的一般关键词：
- 最大值尽量小
- 最小值尽量大
- (在某种情况下)最小值是多少
- (在某种情况下)最大值是多少
说到这里，新手可能有点蒙，没关系，我们来看几个例题：
It is the time to 举栗子！
例题Z：买糖
小朋有个弟弟，小凯。小凯喜欢哭鼻子，经常因为没糖吃而哭鼻子。小朋要哄着小凯，给小凯买糖吃，小朋有 N 元钱，商店老板小康卖的糖 K 元一个，共有 M 个，小凯多吃一块糖就少哭一次，但事实也不是任由小凯的，他吃糖就会把糖纸乱扔，弄得校园很脏，校园里脏的程度y与小凯吃糖个数x关系是：y=x^2-20181314*x,当校园里脏的程度超过 S 时，小凯的姐姐小林就会打她，小凯虽想吃糖但他不想挨打啊，问小凯在不被挨打的情况下，最多可以少哭多少次？
数据范围 1<=K,N,M,S<=10^9
- （这题不要当真，瞎搞用的，测试一波O(N)与O(logN)的差距）
#include <iostream>
#include <cmath>
using namespace std;
long long n,m,k,s;
int ok=1;
bool isok(int z)
{
if(z<=m&&z*k<=n&&2*z<=s)
{
return 1;
}
else return 0;
}
int main()
{
cin>>n>>m>>k>>s;
///朴素查找
for(int i=1;i<=m;i++)
if(!isok(i))
{
cout<<"ans is "<<i<<endl;
ok=0;
break;
}
if(ok)
cout<<"ans is "<<m<<endl;
///二分查找
long long l=1,r=m;
long long ans;
while(l<=r)
{
long long mid=(l+r)/2;
if(isok(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<"ans is "<<ans;
return 0;
}
例题A：安排牛棚 ->链接
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int x[100005];
int c, n;
int R, L = 1e9 + 9;
int s;
int ans;
bool ansok(int key)
{
int now = 1; //now表示上一个放牛的牛棚编号，因为第一次在一号牛棚放下，所以now=1
int sum = 1; //sum表示放的牛的个数，初始时我们肯定把第一个牛棚放上牛，所以sum=1
for (int i = 2; i <= n; i++)
{
if (x[i] - x[now] >= key)
{
sum++;
now = i;
}
}
if (sum >= c)
return 1;
else
return 0;
}
int main()
{
cin >> n >> c;
for (int i = 1; i <= n; i++)
{
scanf("%d", &x[i]);
s = max(s, x[i]);
L = min(L, x[i]);
}
sort(x + 1, x + 1 + n);
R = s / c + 1;
while (L <= R)
{
int mid = (L + R) / 2;
if (ansok(mid))
{
L = mid + 1;
ans = mid;
}
else
R = mid - 1;
}
cout << ans;
return 0;
}
/*
ansok(int key) ：
我们假设key就是最小值，那么我们就尝试按照这样的最小值能不能把牛给安排下
如果两个牛棚之间的距离小于key，那么这个牛棚不能放牛，因为我们已经假设了key是最小值
这个选择的过程不理解的话模拟一下就可以
*/
例题B：跳石头 ->链接
#include <iostream>
#include <algorithm>
using namespace std;
int N, M, L;
int minAns = 1e9 + 9;
int maxAns;
int ans;
int dis[50006];
bool ansok(int key)
{
int sum = 0;
int now = 0;
for (int i = 1; i <= N + 1; i++)
{
if (dis[i] - dis[now] < key)
sum++;
else
now = i;
}
if (sum <= M)
return 1;
else
return 0;
}
int main()
{
cin >> L >> N >> M;
for (int i = 1; i <= N; i++)
{
cin >> dis[i];
}
dis[N + 1] = L; //虚拟一个终点 N+1
int left = 0;
int right = L;
while (left <= right)
{
int mid = (left + right) / 2;
if (ansok(mid))
{
ans = mid;
left = mid + 1;
}
else
{
right = mid - 1;
}
}
cout << ans;
return 0;
}
/*
这题有一个坑在于起点到终点的距离要大于第 N 个点到起点的距离
我们虚拟一个 N+1 点，来判断第 N 个石头是不是要拿走
*/
例题C：组装玩具 ->链接
- 这题可以用二分解决，但不像是之前两个题那么“模板化” ，需要注意的地方要单独处理，本题深入沟通可以私聊我QQ
#include <iostream>
#include <algorithm>
using namespace std;
struct toy
{
int a;
int b;
int c;
} s[1000006];
int n, m;
int cnt;
int ans = 0;
int sum;
int k[1000006];
bool cmp(toy x, toy y)
{
return x.c < y.c;
}
int ifok(int k) //判断二分出的答案是否可行
{
int mm = 0;
for (int i = 0; i < n; i++)
{
if (s[i].c >= k)
return m - mm;
mm += k * s[i].b - s[i].a;
if (m - mm < 0)
return m - mm;
}
return m - mm;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> s[i].a;
for (int i = 0; i < n; i++)
{
cin >> s[i].b;
s[i].c = s[i].a / s[i].b;
sum += s[i].b;
}
sort(s, s + n, cmp);
for (int i = 0; i < n; i++)
{
if (k[cnt] != s[i].c)
k[++cnt] = s[i].c;
}
int mm = ifok(k[cnt] + 1);
if (mm == 0)
cout << cnt + 1;
else if (mm > 0)
cout << mm / sum + k[cnt] + 1;
else //本题核心：二分答案
{
int l = 0;
int r = k[cnt];
while (l <= r)
{
int mid = (l + r) / 2;
if (ifok(mid) >= 0)
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
cout << ans;
}
return 0;
}
cout << "Hello, QLU_ACM_club !!!" << endl;
