[AcWing] 789. 数的范围

标签: 二分

给定一个按照升序排列的长度为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

思路：

没有思路的时候，想想暴力解法（当然这题可以看出是二分），前不久刚学了时间复杂度的估算（假设1s内可以计算10^8次）：

时间复杂度	1s内计算次数
O(N)	10 ^ 8
O(N ^ 2)	10 ^ 4
O(lg N)	27

/*
暴力解法：超时，数据规模最高达到10^ 9
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 10e5 + 10;
int main() {
    int n, m, arr[N], target;
    
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) 
        scanf("%d", &arr[i]);
    
    while(m--) {
        scanf("%d", &target);
        
        int l = -1, r = -1;
        //左, 右边界 10 ^ 5 * 10 ^ 4, O(n)可能会超时,试试吧
        for(int i = 0; i < n; i++) {
            if(l == -1 && arr[i] == target) {
                l = i;
            }
            
            if(i + 1 < n && arr[i + 1] != target && arr[i] == target) { //没有去找 n- 1的位置
                r = i;
            }
        }
        
        if(arr[n - 1] == target) {
            r = n - 1;
        }
        
        //没有找到
        if(l == -1) {
            printf("-1 -1\n");
        } else {
            printf("%d %d\n", l, r);
        }
    }
    return 0;
}

/*
    二分解法
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 10e5 + 10;
int main() {
    int n, m, arr[N], target;
    
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) 
        scanf("%d", &arr[i]);
    
    while(m--) {
        scanf("%d", &target);
        
        //寻找左边界
        int l = 0, r = n - 1;
        while(l < r) {
            int mid = l + ((r - l) >> 1);
            
            if(arr[mid] < target) {
                l = mid + 1;
            } else if(arr[mid] > target) {
                r = mid - 1;
            } else {
                r = mid;
            }
        }
        
        if(arr[l] != target) {  //区间中没有target
            cout << "-1 -1" << endl;
            continue;
        }
        
        cout << l << " ";
        
        //寻找右边界
        l = 0, r = n - 1;
        while(l < r) {
            int mid = l + ((r - l + 1) >> 1);
            
            if(arr[mid] < target) {
                l = mid + 1;
            } else if(arr[mid] > target) {
                r = mid - 1;
            } else {
                l = mid;    //将数组分成[l, mid - 1], [mid + 1, r]，所以 mid = l + ((r - l + 1) >> 1)
            }
        }
        
        cout << l << endl;
    }
    return 0;
}