在Python中的排序数组中查找元素的第一个和最后一个位置

假设我们有一个整数数组A。它按升序排序，我们必须找到给定目标值的开始和结束位置。当在数组中找不到目标时，返回[-1，-1]。因此，如果数组类似于[2,2,2,3,4,4,4,4,5,5,6]，而目标为4，则输出将为[4,7]

为了解决这个问题，我们将遵循以下步骤-

• 最初res：= [-1，-1]，设置low：= 0，high：=数组A的长度

• 从低到高

• 高：=中，res [0]：=中，res [1]：=中

• 中：=低+（高–低）/ 2

• 如果A [mid]是目标，则

• 否则，当A [mid] <目标时，则低：=中+ 1，否则高：=中

• 如果res [0] = -1，则返回res

• 低：= res [0] + 1，高：=长度

• 从低到高

• 低：=中+ 1，res [1]：=中

• 中：=低+（高–低）/ 2

• 如果A [mid]是目标，则

• 否则，当A [mid] <目标时，则低：=中+ 1，否则高：=中

• 返回资源

示例(Python)

让我们看下面的实现以更好地理解-

class Solution(object):
   def searchRange(self, nums, target):
      res = [-1,-1]
      low = 0
      high = len(nums)
      while low<high:
         mid = int(low + (high-low)//2)
         if nums[mid] == target:
            high = mid
            res[0]=mid
            res[1]=mid
         elif nums[mid]<target:
            low = mid+1
         else:
            high = mid
      if res[0] == -1:
         return res
      low = res[0]+1
      high = len(nums)
      while low<high:
         mid = int(low + (high-low)//2)
         if nums[mid] == target:
            low = mid+1
            res[1] = mid
         elif nums[mid] < target:
            low = mid + 1
         else:
            high = mid
      return res
ob1 = Solution()print(ob1.searchRange([2,2,2,3,3,4,4,4,4,5,5,6], 4))

输入值

[2,2,2,3,4,4,4,4,5,5,6]
4

输出结果

[5, 8]