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的長度
  • 當 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))

輸入

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

輸出

[5, 8]

更新於: 2020年4月27日

870 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告