二分查找:二分查找是基于有序序列的查找算法,该算法一开始令[lift,rigth]为整个序列的下标区间,然后每次测试当前[lift,rigth]的中间位置mid=(lift+rigth)/2,判断mid与预查询的元素x的大小。
二分查找的高效之处在于,每一步都可以去除当前区间中的一半元素,因此其时间复杂度是O(logn)。
二分做题模板:
例题1:
789.数的范围
给定一个按照升序排列的长度为n的整数数组,以吸q个查询。对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。如果数组中不存在该元素,则返回 -1 -1 。
输入格式
第一行包含整数n和q,示数组长度和询问个数。
第二行包含n个整数(均在1 ~ 10000范围内),表示完整数组。
接下来q行,每行包含一个整数 k,表示一个询问元素。
输出格式
共q行,行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1 。
数据范围
1≤n≤100000
1 < q≤10000
1 <k< 10000
输入样例:
6 3
1 2 2 3 3 4
3
4
5
输出样例:
3 4
5 5
-1 -1
#include<algorithm> #include<cmath> #include<deque> #include<vector> #include<queue> #include<string> #include<iostream> #include<cstring> #include<map> #include<stack> #include<set> using namespace std; const int N = 100010; int n, q; int a[N]; int main() { cin>>n>>q; for(int i=0;i<n;i++) { cin>>a[i];//遍历数组; } while (q--)// q次查询; { int x; cin>>x;//x就是我们在数组中要找的数 int l=0,r=n-1; while(l<r) { int mid=l+r>>1; //首先要找到>=x的第一个数,这样我们就可以找到第一个数的下标 if(a[mid]>=x)//当a[mid]>= x时,说明mid及其左边可能含有值为x的元素 { r=mid;//所以将mid赋值给r,缩小一半范围 } else { l=mid+1;//否则,就是a[mid]<x,mid在其右侧,所以就将mid+1赋值给l,因为mid<x,所以mid本身不符合,所以mid+1; } } if(a[l]==x)//如果l和r相遇之后,a[l]是等于x的,那么就输出该数下标; { cout<<l<<" "; l=0,r=n-1; while(l<r) { int mid=l+r+1>>1; if(a[mid]<x+1)// 开始寻找<x+1的数,也就是x的最后一个位置; { l=mid;//就说明x+1在mid的右侧,所以将mid赋值给l; } else { r=mid-1;//否则x+1就在mid的左侧,因为mid<x+1,mid本身不符合,所以mid-1; } } cout<<r<<endl;//输出r; } else//如果l和r相遇后的数a[l]!=x,那么就输出-1 -1; { cout<<"-1 -1"<<endl; } } return 0; }
例题2:
题目 1885:
蓝桥杯2017年第八届真题-分巧克力
题目描述
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一.共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见,小明需要从这N块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:
1.形状是正方形,边长是整数
2.大小相同
例如一.块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。.
当然小朋友们都希望得到的巧克力尽可能大,你能帮小Hi计算出最大的边长是多少么?
输入
第一行包含两个整数N和K。(1 <= N, K <=100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。
输出
输出切出的正方形巧克力最大可能的边长。
样例输入
2 10
65
56
样例输出
2
#include<algorithm>
#include<cmath>
#include<deque>
#include<vector>
#include<queue>
#include<string>
#include<iostream>
#include<cstring>
#include<map>
#include<stack>
#include<set>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],w[N];
bool check(int x)//x就是我们要找的最大的边长;
{
int num=0;//我们可以截取的块数;
for(int i=0;i<n;i++)
{
num=num+(h[i]/x)*(w[i]/x);//(h[i]/x)*(w[i]/x)表示的是我们可以截取的块数;
}
if(num>=m)//如果截取的块数大于小朋友的人数;
{
return true;
}
else
{
return false;
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>h[i]>>w[i];//长和宽;
}
int l=1,r=1e5;//l=1是因为输入保证每位小朋友至少能获得一块1x1的巧克力
while(l<r)//套用模板,取得是右侧,向下取整;
{
int mid=l+r+1>>1;
if(check(mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
cout<<l;//最后当l和r相遇时,就输出l或r;
return 0;
}
如果理解有误,请不吝赐教。谢谢!
更多推荐
C++二分知识模板与例题
发布评论