题目描述

给定一个按照升序排列的长度为 $n$ 的有序数组 $a$ 和一个目标值 $x$，查找出这个目标值在有序数组中的第一个位置和最后一个位置。如果在数组中不存在目标值，则输出 [-1,-1]。

• 大家可以手写二分，也可以用 STL 库中提高的二分函数

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {2, 3, 3, 5, 6};
    int k = 3;

    // 查找 a 中第一个大于等于 k 的数的下标; 如果没有, 就返回 n
    // 输出: 1
    cout << lower_bound(a.begin(), a.end(), k) - a.begin() << '\n';

    // 查找 a 中第一个大于 k 的数的下标; 如果没有, 就返回 n
    // 输出: 3
    cout << upper_bound(a.begin(), a.end(), k) - a.begin() << '\n';
    
    // 输出: 5, 也就是数组 a 的大小 n, 因为找不到大于等于 10 的数
    cout << lower_bound(a.begin(), a.end(), 10) - a.begin() << '\n';    
    
    // 输出: 5, 也就是数组 a 的大小 n, 因为找不到大于 10 的数
    cout << upper_bound(a.begin(), a.end(), 10) - a.begin() << '\n';     
    return 0;
}

• 需要注意的是：
• lower_bound(a.begin(), a.end(), k) 返回的是迭代器（类似数组里面的指针）
• 如果想得到下标，可以这样：
  • lower_bound(a.begin(), a.end(), k) - a.begin()
• upper_bound() 同理
• 目标值的第一个位置：
  • lower_bound(a.begin(), a.end(), k) - a.begin()
• 目标值的最后位置：
  • upper_bound(a.begin(), a.end(), k) - a.begin() - 1
  • 也就是第一个 $> k$ 的位置 $-1$

输入格式

输入包含 $2$ 行

第 $1$ 行包 $2$ 个整数，第一个为目标值整数 $x$，第二个为数组的长度 $n$。

第 $2$ 行包含 $n$ 个整数，用空格分开，表示升序排列的数组 $a_1, a_2, ..., a_n$。

输出格式

• 如果目标值存在，则输出第一个和最后一个位置，用空格分开
• 否则，输出 [-1,-1]

8 6
5 7 7 8 8 10

[4,5]

5 6
5 7 7 8 8 10

[1,1]

6 6
5 7 7 8 8 10

[-1,-1]

提示

【样例解释 1】

• 请先用自己写的二分实现
• 再用 lower_bound() 和 upper_bound() 实现
• 不要直接暴力！！

数据规模与限制

• $1 \le n\le 10^4$