一.二分查找
知识点:1.在有序序列中查找数的问题
(1)sort排序
(2)省时间就用库函数,
[库函数]
1.lower_bound(数组名,数组名+长度,x(要找的元素))-数组名
返回数组中第一个大于等于x的下标(注意还是避免用*,而去用减去数组首地址即数组名)
2.upper_bound(a,a+len,x)-a 返回数组第一个大于x的下标
3.binary_search(a,a+n,x) 查找数组中是否有x元素,
如 if(binary_serch(a,a+n,x)) 操作1 else 操作2 (这样数组中有x元素则会执行操作1)
[用模板](当数组中有重复元素时)
int SL(int l, int r, int x) //找第一个等于x的数(思路:既然找第一个那么判断条件一定是a[mid]>=x,条件一定是大于开头,由于数组升序)
{
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
int SR(int l, int r, int x) //找最后一个等于k的数(思路:既然找最后一个那么判断条件一定是a[mid]<=x,条件一定是小于开头,由于数组升序)
{
while (l < r)
{
int mid = l + r + 1 >> 1;//有加必有减
if (a[mid] <= x) l = mid;
else r = mid - 1;
}
return r;
}
【例题】(以下代码均用库函数解的)
1.计蒜客二分查找(一)
题意:在数组当中找等于x的数(比较简单没有模板)
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x;
const int N=1e5+10;
int a[N];
int check(int x)//[返回下标]
{
int l=0,r=n;
while(l<=r)
{
int mid=l+r>>1;
if(a[mid]>=x)r=mid-1;
else l=mid+1;
}
return l;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
while(m--)
{
cin>>x;
int mid=check(x);
if(a[mid]==x)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
2.计蒜客二分查找(二)
题意:这次是找大于等于x的了,法一可以用库函数,法二手写个二分
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x;
const int N=1e5+10;
int a[N];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
while(m--)
{
cin>>x;
int mid=lower_bound(a,a+n,x)-a;
if(a[mid]>=x)cout<<a[mid]<<endl;
else cout<<-1<<endl;
}
return 0;
}
3.计蒜客二分查找(三)
题意:这次找大于x的数
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x;
const int N=1e5+10;
int a[N];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
while(m--)
{
cin>>x;
if(x<a[0])cout<<a[0]<<endl;
else if(x>=a[n-1])cout<<-1<<endl;
else
{
int mid=upper_bound(a,a+n,x)-a;
if(a[mid]>x)cout<<a[mid]<<endl;
else cout<<-1<<endl;
}
}
return 0;
}
4.计蒜客二分查找(四)
题意:这次找等于x的数有多少个,法一库函数,法二可以用上面的模板分别找出下标做差即可
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x;
const int N=1e5+10;
int a[N];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
while(m--)
{
cin>>x;
int l = lower_bound(a, a+n, x)-a;//左边界
int r = upper_bound(a, a+n, x)-a;//右边界(但是取不到相当于左闭右开,所以下面的直接做差不取r)
cout<<r-l<<endl;
}
return 0;
}
5.计蒜客二分查找(五)
题意:找小于等于x的最大值是多少
#include <bits/stdc++.h>
using namespace std;
int x;
const int MAXN = 1e5+6;
int a[MAXN] = {};
int main() {
int n,m;
scanf("%d%d", &n, &m);
int i;
for (i=0; i<n; i++) {
scanf("%d", &a[i]);
}
sort(a, a+n);
while(m--)
{
cin>>x;
if(x<a[0])cout<<-1<<endl;//特判 小于左边界
else if(x>a[n-1])cout<<a[n-1]<<endl; //特判 大于右边界
else
{
if(binary_search(a,a+n,x))cout<<x<<endl;//先看x是不是在数组中,如果在的话就直接输出x即可(因为大于等于xde)
else
{
int pos=upper_bound(a,a+n,x)-a;//如果x不在序列中,那找第一个大于x的数,因为单调,则这个pos前面的数一定小于x,因为x不在序列中,所以用upper
cout<<a[pos-1]<<endl;
}
}
}
return 0;
}
6.计蒜客二分查找(六)
题意:找比x小的最大值
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+6;
int a[N];
int main() {
int n,m;
scanf("%d%d", &n, &m);
int i;
for (i=0; i<n; i++) {
scanf("%d", &a[i]);
}
sort(a, a+n);
for (i=0; i<m; i++) {
int x;
scanf("%d", &x);
if (x<=a[0]) {//这次等于不符合题意
printf("-1\n");
} else if (x>a[n-1]) {
printf("%d\n", a[n-1]);
}
else
{
int pos;
if (binary_search(a, a+n, x))
{
//存在x
pos = lower_bound(a, a+n, x)-a;//找第一个大于等于
}
else
{
//不存在x
pos = upper_bound(a, a+n, x)-a;//找第一个大于
}
printf("%d\n", a[pos-1]);//找到的数的前一个
}
}
return 0;
}
注意模板代入左右端点时,与数组下标左右端点相同