摘要
Title: 789. 数的范围
Tag: 二分
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

789. 数的范围

• 题意

  给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
  对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
  如果数组中不存在该元素，则返回 -1 -1。

• 思路

  整数二分即可，如果二分出的值和原数不相等，就说明没找到

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-02-19 12:03:04
  FilePath: \ACM\Acwing\789.py
  LastEditTime: 2022-02-19 21:06:19
  '''
  
  from collections import Counter
  
  a = []
  
  
  def findl(x):
      l = 0
      r = len(a) - 1
      while l < r:
          mid = l + r >> 1
          if a[mid] >= x:
              r = mid
          else:
              l = mid + 1
      return r
  
  
  def findr(x):
      l = 0
      r = len(a) - 1
      while l < r:
          mid = l + r + 1 >> 1
          if a[mid] <= x:
              l = mid
          else:
              r = mid - 1
      return r
  
  
  if __name__ == "__main__":
      n, q = map(int, input().split())
      a = list(map(int, input().split()))
      for i in range(q):
          x = int(input())
          L = findl(x)
          R = findr(x)
          if a[L] != x or a[R] != x:
              print(-1, -1)
          else:
              print(L, R)