ac_789数的范围

题目描述

题目大意&链接

给定一个长度为 n 的整数数列以及 q 个查询，对于每个查询，返回元素 k 的起始和终止位置，若 k 不存在返回-1 -1）。

输入输出样例：
输入：

6 3
1 2 2 3 3 4
3
4
5

输出：

3 4
5 5
-1 -1

详情：ac_789数的范围

解题思路

需要用到两次二分分别查询元素 k 的起始和终止位置。

1. 查询元素 k 的起始位置：

   int bsearch_1(int l, int r, int k)
   {
       //通过 mid = l + r >> 1 和 r = mid 确保向左收缩，找到左边界。
       while(l < r)
       {
           int mid = l + r >> 1;
           if(q[mid] >= k) r = mid;
           else l = mid + 1;
       }
   
       if(q[l] != k) return -1;
       else return l;
   }

2. 查询元素 k 的终止位置：

   int bsearch_2(int l, int r, int k)
   {
       //mid = l + r + 1 >> 1 和 l = mid 确保向右收缩，找到右边界。
       while(l < r)
       {
           int mid = l + r + 1 >> 1;
           if(q[mid] <= k) l = mid;
           else r = mid - 1;
       }
   
       if(q[l] != k) return -1;
       else return l;
   }

完整代码

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int q[N];

int bsearch_1(int l, int r, int k)
{
    while(l < r)
    {
        int mid = l + r >> 1;
        if(q[mid] >= k) r = mid;
        else l = mid + 1;
    }
    
    if(q[l] != k) return -1;
    else return l;
}

int bsearch_2(int l, int r, int k)
{
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(q[mid] <= k) l = mid;
        else r = mid - 1;
    }
    
    if(q[l] != k) return -1;
    else return l;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    while(m--)
    {
        int k;
        scanf("%d", &k);
        
        int l = bsearch_1(0, n-1, k);
        if(l != -1){
            int r = bsearch_2(0, n-1, k);
            cout<<l<<" "<<r<<endl;
        }
        else
        {
            cout<<-1<<" "<<-1<<endl;
        }
    }
    return 0;
}

时间和空间复杂度

时间复杂度：O(logn)
空间复杂度：O(n)