基础算法复习:整数二分
题目描述
给定一个按照升序排列的长度为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
写代码之前
先简单看一下题目,意思是要我们查找某个数最先出现和最后出现的位置并输出,如果不存在则输出”-1 -1”。容易想到的一个办法是二分查找。要进行二分查找,需要这个区间有以是否符合某种性质S为标准的区间的分界点,即在区间的一侧都满足性质S(包括分界点),而在另一侧都不满足性质S,这个分界点就是我们要查找的值。题目给定的是一个升序的数组,以第一个出现的给定数k为分界点,容易得到性质S就是是否大于等于k,而显然分界点左边的数都小于k,右边的都大于等于k。以最后出现的该数k为分界点,性质S是是否小于等于k,显然分界点左边的数都小于等于k,右边都大于k。因此本题使用二分查找。
算法
二分查找的过程就是不断对区间中点进行是否符合性质S的判断,每次选择答案所在的一半区间,而舍弃另一半区间,直到最后得到长度为1的答案区间,此时的数就是答案。二分查找最后一定会查出来一个数,二分查找本身一定有解,但是题目情况可能无解。因此本题查找完还要进行一个判断。
两个模板的选择
两个模板的差异就在于l和r的更新方式,以及mid的计算方式一个是mid=l+r+1>>1,另一个是l+r>>1。l,r更新方式画个图看看就看出来了,主要是mid计算时是否要加一这里的选择。记忆时只要记得更新时l=mid的话就要加一就可以了,如果要追究其原因的话,是因为整除的向下取整的性质,如果l+r-1==2l,那么(l+r>>1)==l,然后mid满足S性质,更新之后的区间仍然等于原区间,这样就进入了无限循环,+1之后才能有效改变l,逐步缩小区间。
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N=100010;
int q[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)scanf("%d",&q[i]);
while(m--){
int k;
scanf("%d",&k);
int l=0,r=n-1;
while(l<r){
int mid=l+r>>1;
if(q[mid]>=k) r=mid;
else l=mid+1;
}
if(q[l]!=k) cout<<"-1 -1"<<endl;
else{
cout<<l<<' ';
int l=0,r=n-1;
while(l<r){
int mid=l+r+1>>1;
if(q[mid]<=k) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
}
return 0;
}