二分查找（STL函数+模板+刷题）
二分查找（STL函数+模板+刷题）
二分查找是一种在有序数组中查找某一元素的算法。本文将从STL函数、模板以及实际刷题应用三个方面，详细介绍二分查找的原理和使用方法。
二分查找（STL函数+模板+刷题）
二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。
模板题目描述
输入n nn个不超过1 0 9 10^9109的单调不减的（就是后面的数字不小于前面的数字）非负整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_{n}a1 ,a2 ,…,an ，然后进行m mm次询问。对于每次询问，给出一个整数q qq，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出− 1 -1−1。
输入格式
第一行2 22个整数n nn和m mm，表示数字个数和询问次数。
第二行n nn个整数，表示这些待查询的数字。
第三行m mm个整数，表示询问这些数字的编号，从1 11开始编号。
输出格式
输出一行，m mm个整数，以空格隔开，表示答案。
输入输出样例 #1
输入 #1
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
输出 #1
1 2 -1
说明/提示
数据保证，1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^61≤n≤106，0 ≤ a i , q ≤ 1 0 9 0 \leq a_i,q \leq 10^90≤ai ,q≤109，1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^51≤m≤105
本题输入输出量较大，请使用较快的 IO 方式。
STL自带函数
不会写二分或者懒得写，那就用
STL
自带的二分函数——
upper_bound
和
lower_bound
。
这两个函数的作用是二分查找一个数在数组中出现的位置。区别是
upper
返回第一个大于搜索数的位置，而
lower
是第一个大于等于的数的位置。
如果我们想要查找值为x的地址，稍加思考，就知道可以写：
lower_bound(a.begin(),a.end(),x)
返回第一个大于等于x的数的地址。而由于是地址，在最后要 −a（也就是减去地址）。
#include<cstdio>
#include<algorithm>//用到lower_bound
using namespace std;
const int MAXN=1e6+10;//注意范围
int read(){//快读
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int a[MAXN];
int main(){
int n=read(),m=read();//读入
for(int i=1;i<=n;i++) a[i]=read();
while(m--){
int x=read();
int ans=lower_bound(a+1,a+n+1,x)-a;//二分搜，注意-a
if(x!=a[ans]) printf("-1 ");//没有，输出-1
else printf("%d ",ans);//有，输出ans
}
return 0;//华丽结束
}
解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了「二分答案」。
二分答案题的几个特征:
(1)求最大/最小值;
(2)答案离散(答案有有限种可能);
(3)容易判断答案是否正确(事实上,这题如果要写SPJ,只需要满足ans满足条件但ans+1不满足条件即可)。
一般的二分模板
int bsearch(int left, int right)
{
while (left <= right)
{
int mid = left + right >> 1;
if (check(mid)) left = mid + 1;
else right = mid - 1;
}
return left或right
}
无论是求左边界还是右边界都是这一套写法
区别在于
如果要求的是左边界，那么就返回left
如果要求的是右边界，那么就返回right
P1873 [COCI 2011/2012 #5] EKO / 砍树
题目描述
伐木工人 Mirko 需要砍M MM米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数H HH（米），伐木机升起一个巨大的锯片到高度H HH，并锯掉所有树比H HH高的部分（当然，树木不高于H HH米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为20 , 15 , 10 20,15,1020,15,10和17 1717，Mirko 把锯片升到15 1515米的高度，切割后树木剩下的高度将是15 , 15 , 10 15,15,1015,15,10和15 1515，而 Mirko 将从第1 11棵树得到5 55米，从第4 44棵树得到2 22米，共得到7 77米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度H HH，使得他能得到的木材至少为M MM米。换句话说，如果再升高1 11米，他将得不到M MM米木材。
输入格式
第1 11行2 22个整数N NN和M MM，N NN表示树木的数量，M MM表示需要的木材总长度。
第2 22行N NN个整数表示每棵树的高度。
输出格式
1 11个整数，表示锯片的最高高度。
输入输出样例 #1
输入 #1
4 7
20 15 10 17
输出 #1
15
输入输出样例 #2
输入 #2
5 20
4 42 40 26 46
输出 #2
36
说明/提示
对于100 % 100%100%的测试数据，1 ≤ N ≤ 1 0 6 1\le N\le10^61≤N≤106，1 ≤ M ≤ 2 × 1 0 9 1\le M\le2\times10^91≤M≤2×109，树的高度≤ 4 × 1 0 5 \le 4\times 10^5≤4×105，所有树的高度总和> M >M>M。
solution
#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long h[1000010];
bool check(long long mid){
long long t=0;
for(int i=1;i<=n;i++){
if(mid<h[i])t+=h[i]-mid;
}
if(t>=m) return true;
else return false;
}
int main(){
cin>>n>>m;
long long r=0,l=1;
for(int i=1;i<=n;i++){cin>>h[i];r=max(r,h[i]);}
while(l<=r){
long long mid=(l+r)/2;
if(check(mid)){
l=mid+1;
}
else {
r=mid-1;
}
}
cout<<l-1;
return 0;
}
这个代码用到了模板。
P2440 木材加工
题目背景
要保护环境
题目描述
木材厂有n nn根原木，现在想把这些木头切割成k kk段长度均为l ll的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出l ll的最大值。
木头长度的单位是cm \text{cm}cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为11 1111和21 2121，要求切割成等长的6 66段，很明显能切割出来的小段木头长度最长为5 55。
输入格式
第一行是两个正整数n , k n,kn,k，分别表示原木的数量，需要得到的小段的数量。
接下来n nn行，每行一个正整数L i L_iLi ，表示一根原木的长度。
输出格式
仅一行，即l ll的最大值。
如果连1cm \text{1cm}1cm长的小段都切不出来，输出
0
。
输入输出样例 #1
输入 #1
3 7
232
124
456
输出 #1
114
说明/提示
数据规模与约定
对于100 % 100%100%的数据，有1 ≤ n ≤ 1 0 5 1\le n\le 10^51≤n≤105，1 ≤ k ≤ 1 0 8 1\le k\le 10^81≤k≤108，1 ≤ L i ≤ 1 0 8 ( i ∈ [ 1 , n ] ) 1\le L_i\le 10^8(i\in[1,n])1≤Li ≤108(i∈[1,n])。
solution
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int arr[N];
long long int check(int m,int *arr,int n){
long long int sum=0;
for(int i=1;i<=n;i++ ){
if(arr[i]>=m)sum+=(int)(arr[i]/m);
}
return sum;
}
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>arr[i];
int min=arr[1];
for(int i=1;i<=n;i++){
if(arr[i]>=min)min=arr[i];
}
int l=1,r=min;
while(l<=r){
int mid=(l+r)/2;
long long int num=check(mid,arr,n);
if(num>=k){
l=mid+1;
}else{
r=mid-1;
}
}
cout<<r;
return 0;
}
本题显然是要求右边界，所以输出r.
本文原文来自CSDN