AcWing 789. 数的范围
原题链接
简单
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std ;
const int N = 100010 ;
int st[N] ;
int n , q ;
int search1(int target) {
int left = 1, right = n ;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (st[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (st[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (st[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 判断 target 是否存在于 nums 中
// 此时 target 比所有数都大,返回 -1
if (left == n + 1) return -1;
// 判断一下 nums[left] 是不是 target
return st[left] == target ? left - 1 : -1;
}
int search2(int target) {
int left = 1, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (st[mid] < target) {
left = mid + 1;
} else if (st[mid] > target) {
right = mid - 1;
} else if (st[mid] == target) {
// 这里改成收缩左侧边界即可
left = mid + 1;
}
}
// 最后改成返回 left - 1
if (left - 1 < 1) return -1;
return st[left - 1] == target ? (left - 2) : -1;
}
int main ()
{
scanf ("%d%d" ,&n , &q) ;
for (int i = 1 ; i <= n ; i++) scanf ("%d" , &st[i]) ;
int num ;
while (q--){
scanf ("%d" , &num) ;
int left = search1 (num) ;
int right = search2 (num) ;
printf ("%d %d\n" , left , right) ;
}
return 0 ;
}