题目描述

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

算法1

1. 找右边第一个
   也就是满足右边的元素都要大于等于x, 这时为了保证答案在区间内，要更新到区间[l, mid] (r=mid)中。
2. 找左边最后一个
   满足左边的元素都小于等于x，这时要更新到区间[mid, r]（l=mid）中.
3. 最后要判断结果是否满足条件
   Leetcode 704

Python 代码

n, m = map(int, input().split())
seq = list(map(int, input().split()))

def getLeftPosition(seq, target):
    l, r = 0, n-1
    while l < r:
        mid = (l + r) //2
        if seq[mid] >= target:
            r = mid
        else:
            l = mid + 1
    return l

def getRightPosition(seq, target):
    l, r = 0, n-1
    while l < r:
        mid = (l + r + 1) //2
        if seq[mid] <= target:
            l = mid
        else:
            r = mid - 1
    return l

for i in range(m):
    target = int(input())
    left = getLeftPosition(seq, target)
    right = getRightPosition(seq, target)
    if seq[left] != target or seq[right] != target:
        print('-1 -1')
    else:
        print(left, right)