Python實現旋轉排序陣列中的搜尋

假設我們有一個按升序排序的陣列，該陣列在某個未知的樞軸點進行了旋轉。例如，如果陣列類似於 [0,0,1,2,2,5,6]，則它可能變成 [2,5,6,0,0,1,2]。我們需要搜尋一個目標值。如果在陣列中找到該值，則返回 true，否則返回 false。因此，如果陣列類似於 [2,5,6,0,0,1,2]，並且目標值為 0，則輸出為 true。

讓我們看看步驟：

  • low := 0，high := 陣列大小
  • 當 low < high 時
    • mid := low + (high - low) / 2
    • 如果 nums[mid] = target，則返回 true
    • 如果 nums[low] = nums[mid] 且 nums[high - 1] = nums[mid]，則
      • low 加 1，high 減 1，繼續下一次迭代
    • 如果 nums[low] <= nums[mid]，則
      • 如果 target >= nums[low] 且 target < nums[mid]，則 high := mid，否則 low := mid + 1
    • 否則
      • 如果 target <= nums[high - 1] 且 target > nums[mid]，則 low := mid + 1，否則 high := mid
  • 返回 false

讓我們看看下面的實現，以便更好地理解：

示例

線上演示

class Solution(object):
   def search(self, nums, target):
      low = 0
      high = len(nums)
      while low<high:
         mid = low + (high-low)//2
         if nums[mid] == target:
            return True
         if nums[low] == nums[mid] and nums[high-1] == nums[mid]:
            low +=1
            high -=1
            continue
         if nums[low]<=nums[mid]:
            if target >=nums[low] and target <nums[mid]:
               high = mid
            else:
               low = mid+1
         else:
            if target<=nums[high-1] and target>nums[mid]:
               low = mid+1
            else:
               high = mid
      return False
ob1 = Solution()
print(ob1.search([2,5,6,0,0,1,2], 0))

輸入

[2,5,6,0,0,1,2]
0

輸出

True

更新於：2020年5月4日

259 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告