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

pythonserver side programmingprogramming更新于 2025/10/25 15:40:17

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

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

最初 res := [-1,-1]，设置 low := 0，high := 数组 A 的长度
当 low < high
- mid := low + (high – low)/2
- 如果 A[mid] 是目标，则
  - high := mid, res[0] := mid 且 res[1] := mid
- 否则当 A[mid] < 目标时，则 low := mid + 1，否则 high := mid
如果 res[0] = -1，则返回 res
low := res[0] + 1，high := nums 的长度
当 low < high
- mid := low + (high – low)/2
- 如果 A[mid] 是目标，则
  - low := mid + 1, res[1] := mid
- 否则当 A[mid] < 目标时，则 low := mid + 1，否则 high := mid
返回 res

示例 (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))