526互联

数的范围

发布时间 2023-06-28 11:55:53作者: INnoVation-V2

数的范围

给定一个升序数组和一个值，

找出这个值在数组中出现的起始和终止位置，如果不存在，返回-1 -1

分析

假定数组长度是n, 整数是target

首先找出起始位置，即找出满足条件的左边界，以以下数组为例

1 2 3 3 3 3 4
target = 3

左边界右边的数据显然满足>= target

使用第一个模板

int l = 0, r = n - 1;
while(l < r){
  int mid = l + r >> 1;
  if(s[mid] >= target) r = mid;
  else l = mid + 1;
}

然后找出终止位置，即找出满足条件的右边界， 使用第二个模板

int l = 0, r = n - 1;
while(l < r){
  int mid = l + r + 1 >> 1;
  if(s[mid] <= target) l = mid;
  else r = mid - 1;
}

综上

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int s[N];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> s[i];
    while(m--){
        int target;
        cin >> target;
        
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(s[mid] >= target) r = mid;
            else l = mid + 1;
        }
        
        if(s[l] != target){
            cout << "-1 -1" << endl;
            continue;
        }
        cout << l << " ";
        
        l = 0, r = n - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(s[mid] <= target) l = mid;
            else r = mid - 1;
        }
        cout << r << endl;
    }
}