蓝桥杯学习记录||789. 数的范围

2023-10-24 08:16:58

AcWing||789. 数的范围

活动地址：https://www.acwing.com/activity/content/19/

考察要点：二分查找

题目要求

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

题目地址：https://www.acwing.com/problem/content/description/791/

解析：就是在一个升序的整数数组中查找一个数所在的起始位置和结束位置，进行输出。
因为是有序数组，可以二分查找找出数据所在的位置。

思路：先用二分查找，找出qu（要查的数据）的起始位置，再在求出起始位置的基础上，继续用二分查找求出结束位置。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
 using namespace std;
 const int N = 100010;
 int num[N];
 int n,q;
int main()
{   
    cin >> n >> q;
    for (int i = 0; i < n; i ++ ) scanf("%d", &num[i]);
    
    while (q -- )
    {
        int qu;  //要查的数
        scanf("%d", &qu);
        //先二分查找左端点
        int l = 0, r = n - 1;   //确定区间范围
        while(l < r)
        {
            int mid = l + r >> 1;  //取中
            if(num[mid] < qu)  l = mid + 1;
            else r = mid;
        }
        if(num[l] == qu)
        {
            cout << l << " ";  //找到了左端点
            //找右端点
            r = n - 1;  //右端点区间为 l 到 n-1
            while (l < r)
            {
                int mid = l + r + 1 >> 1;  //向上取整 避免死循环
                if(num[mid] > qu) r = mid - 1;
                else l = mid;
            }
            cout << l << endl;
        }
        else{
            cout << "-1 -1" << endl;
        } 
        
    }
    return 0;
}

代码解析起始端点查找

    while(l < r)
     {
         int mid = l + r >> 1;          //取中， +号的优先级高于 >>
         if(num[mid] < qu)  l = mid + 1;   
         else r = mid;
     }