二分查找
ACM题集：https://blog.csdn.net/weixin_39778570/article/details/83187443
出自蓝桥学苑 GtDzx老师
#二分查找（1）
假设数组a[0], a[1], … a[n-1]是单调递增的，并且没有重复的数值。要求在a数组中查找x，如果x存在，返回对应的下标；否则输出-1。
#include <iOStream>
using namespace std;
int n, x, a[100010];
int binary_search(int* a, int n, int x){ // 闭区间
int ans = -1;
int l=0, r=n-1;
while(l <= r){
int m = l + ((r-l)>>1);
if(a[m]==x){
ans = m;
break;
}
if(a[m]<x){
l=m+1;
}else{
r=m-1;
}
}
return ans;
}
int main(){
cin >> n >> x;
for(int i=0; i<n; i++) cin >> a[i];
int ans = binary_search(a, n, x);
cout << ans << endl;
return 0;
}
#二分查找（2）
C++ STL提供了两个特别好用的函数：lower_bound()和uppper_bound()。假设a是一个数组，n是数组长度，lower_bound(a, a+n, x)返回数组a[0]~a[n-1]中，大于等于x的数中，最小的数的指针。由于指针可以通过加减算偏移量，所以我们再减去a(数组名会被隐式转换成指针)，就得到了相应的下标。我们看一下下面的例子，假设我们在a数组中找3这个数。
>>另一个函数叫做upper_bound()。同样假设a是一个数组，n是数组长度，upper_bound(a, a+n, x)返回数组a[0]~a[n-1]中，大于x的数中，最小的数的指针。注意lower_bound是“大于等于”，upper_bound是“大于”。我们看一下下面的例子，假设我们在a数组中找3这个数。
举例:
#include <algorithm>
#include <iostream>
using namespace std;
int main(){
int a[10] = {1,2,2,3,3,3,4,4,4,4};
int n = 10;
for(int i=0; i<=5; i++){
int* lower = lower_bound(a, a+n, i);
int* upper = upper_bound(a, a+n, i);
cout << lower-a << " " << upper-a << endl;
}
/*
0 0
0 1
1 3
3 6
6 10
10 10
*/
另外lower_bound和upper_bound的前两个参数是其实是待查范围的首尾指针(左闭右开区间，不包括尾指针)，所以也可以写别的参数。比如下面的程序就是从a[1]开始查找：
#include <algorithm>
#include <iostream>
using namespace std;
int main(){
int a[10] = {1,2,2,3,3,3,4,4,4,4};
int n = 10;
for(int i=0; i<=5; i++){
int* lower = lower_bound(a+1, a+n, i);
int* upper = upper_bound(a+1, a+n, i);
cout << lower-a << " " << upper-a << endl;
}
}
/*
1 1
1 1
1 3
3 6
6 10
10 10
*/
lower_bound和upper_bound除了能用在数组上，还可以用在vector上。我们知道vector就相当于一个可以长度可变的数组。当用于vector上时，需要注意前两个参数必须是vector的迭代器，同时函数的返回值也是迭代器：
#include <algorithm>
#include <iostream>
using namespace std;
int main(){
int a[10] = {1,2,2,3,3,3,4,4,4,4};
vector<int> b(a, a+10);
int n = 10;
for(int i=0; i<=5; i++){
vector<int>::iterator lower = lower_bound(b.begin(), b.end(), i);
vector<int>::iterator upper = upper_bound(b.begin(), b.end(), i);
cout << lower-b.begin() << " " << upper-b.begin() << endl;
}
return 0;
}
/*
0 0
0 1
1 3
3 6
6 10
10 10
*/
注意my_lower_bound和C++STL自带的lower_bound有区别，my_lower_bound的第一个参数是一个数组，第二个参数是数组长度，第三个参数是待查找的值；它的返回值是“大于等于x的数中，最小的数的下标“，另一个等价的说法是“假设在a数组中插入x，并保持插入后仍然有序，最小的合法插入下标”。实现:
#include <iostream>
using namespace std;
int n, x, a[100010];
int my_lower_bound(int a[], int n, int x){
int ans = n;
int l=0, r=n-1;
while(l<=r){
int m = l + ((r-l)>>1);
if(a[m]>=x){
ans = m;
r = m-1;
}else{
l = m+1;
}
}
return ans;
}
int main(){
cin >> n >> x;
for(int i=0; i<n; i++) cin >> a[i];
int lower = my_lower_bound(a, n, x);
cout << lower << endl;
return 0;
}
以上是my_lower_bound的代码，如果我们要实现my_upper_bound的代码，其实也很容易。my_lower_bound是找“大于等于x的数中，最小的数的下标“，所以是if(a[m] >= x)。
my_upper_bound是找“大于x的数中，最小的数的下标“，所以只需要把f(a[m] >= x)改成if(a[m]>x)即可。
#include <iostream>
using namespace std;
int n, x, a[100010];
int my_upper_bound(int a[], int n, int x){
int ans = n;
int l=0, r=n-1;
while(l<=r){
int m = l + ((r-l)>>1);
if(a[m]>x){
ans = m;
r = m-1;
}else{
l = m+1;
}
}
return ans;
}
int main(){
cin >> n >> x;
for(int i=0; i<n; i++) cin >> a[i];
int lower = my_upper_bound(a, n, x);
cout << lower << endl;
return 0;
}
#二分查找（3）
例题:分巧克力：http://lx.lanqiao.cn/problem.page?gpid=T441
/*分巧克力*/
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int maxn=1e5;
int n,k,w[maxn+5],h[maxn+5];
// 判断时候能分配成功
bool ok(int a){
ll ret=0,num1,num2;
fo(i,1,n){
num1 = w[i]/a; // 宽能分几块
num2 = h[i]/a; // 长能分几块
ret += num1*num2; // 该巧克力能分为几块边长为a的巧克力
if(ret>=k)return true;
}
return ret>=k;
}
// 二分过程
void solve(){
int l=1,r=100001,mid, ans=1; // l,r 为二分上下界
while(l<=r){
mid = l + ((r-l)>>1); // 取中间值
if(ok(mid)){
ans = mid;
l = mid+1;
}else{
r = mid-1;
}
}
printf("%d\n",ans);
}
int main() {
scanf("%d%d",&n,&k);
fo(i,1,n){
scanf("%d%d",&w[i],&h[i]);
}
solve();
return 0;
}
#1357 : 小Ho的防护盾 http://hihocoder.com/problemset/problem/1357
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho的虚拟城市正在遭受小Hi的攻击，小Hi用来攻击小Ho城市的武器是一艘歼星舰，这艘歼星舰会以T(T为大于0的整数)个单位时间的间隔向小Ho的城市轰击。歼星舰总共有N枚炮弹，其中第i枚会造成Ai点伤害值。
幸好小Ho的城市有K层护盾，每层护盾可以抵挡M点伤害。当某次轰击使得伤害值达或超过M时，该层护盾就会被击碎；该次轰击溢出的伤害不会作用于下一层护盾；下一次轰击将由下一层护盾承受。
同时，受损但尚未被击碎护盾会以每单位时间减少1点伤害值的速度修复自己，直到伤害值降为0。这就意味着小Hi的攻击间隔T越大，小Ho撑过这N枚炮弹的可能性就越大。
那么问题来了，小Hi的攻击间隔T至少需要是多少，小Ho城市的防护护盾才能不被全部击破？
为了使题目不存在歧义，规定：
小Hi的第i次攻击发生在时刻(i-1)*T
小Ho的第i次修复发生在时刻i-0.5
输入
第一行包含3个整数N、M和K，意义如前文所述。
第二行包含N个整数A1 - AN，表示小Hi第i枚炮弹的伤害值。
对于30%的数据，满足N<=100
对于100%的数据，满足1<=N<=100000
对于100%的数据，满足1<=K<=10, 1<=Ai, M<=100000
输出
输出使得小Ho城市的防护护盾不被全部击破的小Hi攻击间隔的最小值。如果不存在这样的T，则输出-1。
样例输入
3 5 1
3 3 3
样例输出
3
#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int maxn=1e5;
int n,m,k,a[maxn+5];
bool ok(int T){
int res = k, now=m;
fo(i,1,n){
if(a[i]>=now){ // 破坏掉了，换下一个护盾
now = m;
res--;
if(res<=0)return false;
}else{
now = min(m, now-a[i]+T);
}
}
return res>0;
}
// 有解情况
void solve(){
// 间隔最大为m,间隔最小为1！！！ 二分的区间一定要认真审阅，往往这就是隐藏的错误，不易发现
//小Hi的第i次攻击发生在时刻(i-1)*T 所以二分区间不包含0 (题目也规定了T大于0)
// 小Ho的第i次修复发生在时刻i-0.5
int l=1,r=m,mid,ans=m;
while(l<=r){
mid = l + ((r-l)>>1);
if(ok(mid)){
ans = mid;
r = mid-1;
}else{
l = mid+1;
}
}
printf("%d\n",ans);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
int ret = 0;
fo(i,1,n){
scanf("%d",&a[i]);
if(a[i]>=m)ret++;
}
// 超过k枚导弹能直接击穿护盾
if(ret>=k){
puts("-1");
return 0;
}
solve();
return 0;
}
相关阅读
二叉排序树 二叉排序树（Binary Search Tree，BST）：又称二叉查找树，是一种高效的数据结构。 定义 二叉排序树或者是一棵空树，或者是具有
遇见任何事情，第一件要做的事情都是搜索搜索心法1、找什么？准确描述搜索目标，纠正搜索思维。比如临时要办一个读书讲座没有头绪，就
在某些时候，可能会涉及在海量数据中的查找，如果采用通常的做法，则很难达到一定的效果，在实际工程实践中，海量数据的查找性能很肯恩鬼成
1、instr()函数的格式 （俗称：字符查找函数） 格式一：instr( string1, string2 ) / instr(源字符串, 目标字符串) instr(v_zh_c
二分查找： 即每次用比较区域中间的数值和要查找的数值作比较。用函数调用，程序更加简洁，可移植性增强。令查找这个函数模块返回一个