题目描述
二分查找模版题,关键点:边界
样例
#include <iostream>
using namespace std;
const int N = 100010;
int n, k;
int q[N];
int main()
{
scanf("%d%d", &n , &k);
for(int i = 0 ; i < n; i++) scanf("%d", &q[i]);
while( k -- )
{
int x;
scanf("%d", &x);
int l = 0, r = n - 1;
while( l < r)
{
int mid = l + r >> 1;
/*以 x==3 举例:
如果满足了q[mid]>=3,即mid满足了右边的性质
那么应该将[l, r] 这个区间更新为 [l, mid]
否则mid不满足右边性质,那么mid在边界点左边,区间要更新为[mid + 1, r]
(为什么是mid + 1? 因为mid在不满足的区间内是肯定去不到mid这个点的)
*/
if(q[mid] >= x) r = mid;
else l = mid + 1;
}
//二分是一定有解的即使找不到x也会在当前[l, r]区间内尽可能找到符合>=x的数,
//如果在数组中找不到x则说明该数不在数组中
if(q[l] != x) puts("-1 -1");
else {
//到这一步我们找的是>=x的最小的数,也就是x出现的起始位置,那么将l输出
printf("%d ", l);
//接下来找<=x最大的数,可以找到x出现的终止位置
int l = 0, r = n - 1;
while(l < r)
{
/*这里为什么要 “+1” ?
由于c++是向下取整的计算,
如果不加1,那么mid是可以去到l的,
到了下面的if判断如果成立,会出现l=l无限死循环下去
*/
int mid = l + r + 1 >> 1;
//mid满足左半边的性质,区间应该更新为mid到最右边边界点这段区间,区间划分为[mid, r]
if(q[mid] <= x) l = mid;
else r = mid - 1; //区间更新为[l, mid - 1]
}
//输出x出现的终止位置
printf("%d\n", l);
}
}
return 0;
}