题目特征描述
(1)整数二分:元素都是整数,并且元素之间是断续的,没有交点;
(2)有单调性的数据集合,可以用二分法;但使用二分法,数据不一定非要单调性;
(3)需注意题目中所要求的区间性质,如本题,一种数字可能有多个,存在最右边和最左边的问题,也可以考察数量等问题
解题思路
(1)找中间值 $mid=\frac{l+r}{2}$ 或$mid=\frac{l+r+1}{2}$ ;”<< x或>>x”:”左移或右移x个bit位”,即“数字扩大或缩小2倍”;[移位运算符在加减运算符之后计算]
(2)找一个数 用一次二分法即可。本题存在最右边或最左边的情况,需要用两次二分法。处于不同区间,条件表达式有所不同,具体分析如上图。
【考虑数据在左区间时,l+r+1
,加1是为了防止落入死循环】
(3)二分法循环结束的状态[while(l<r)的结束条件]是l=r ; 当数据不存在时,即a[l]!=x
;
算法1
时间复杂度 $O(log_2n)$
C++ 代码
/*
数的范围
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回 -1 -1。
*/
#include<iostream>
using namespace std;
const int N = 100010;
int n,q;
int a[N];
int main()
{
//input
cin>>n>>q;
for(int i = 0;i < n;i++) cin>>a[i];
//processing
while(q--)
{
int x;
cin>>x;
int l = 0 ;int r = n-1;
//找最左边,满足条件的数,循环结束的状态l = r
while(l < r)
{
int mid = l + r >> 1;
if(a[mid]>=x) r = mid;
else l = mid + 1;
}
if(a[l]!=x) cout<<"-1 -1"<<endl;
else
{
cout<<l<<" ";
int l = 0 ;int r = n-1;
//找最右边,满足条件的数
while(l<r)
{
int mid = l + r + 1 >> 1;
if(a[mid]<=x) l = mid;
else r = mid - 1;
}
cout<<l<<endl;
}
}
return 0;
}