Python旋轉排序陣列中的搜尋

假設我們有一個按升序排序的陣列，並且它在某個未知的樞軸點旋轉了。例如，[0,1,2,4,5,6,7]可能會變成[4,5,6,7,0,1,2]。我們給定一個目標值進行搜尋。如果我們在陣列中找到它，則返回它的索引，否則返回-1。我們可以假設陣列中不存在重複元素。因此，如果陣列類似於[4,5,6,7,0,1,2]，則輸出將為4，因為該元素的索引位於索引4處。

為了解決這個問題，我們將遵循以下步驟：

  • low := 0 high := 陣列長度
  • 當 low < high
    • 找到 mid: mid := low + (high - low)/2
    • 如果 arr[mid] = target，則返回 mid
    • 如果 arr[low] <= arr[mid]
      • 如果 target >= arr[low] 且 target < arr[mid]，則 high := mid，否則 low := mid + 1
    • 否則
      • 如果 target <= arr[high - 1] 且 target > arr[mid]，則 low := mid + 1，否則 high := mid
  • 返回 -1

示例(Python)

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

 線上演示

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 mid
         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 -1
ob1 = Solution()
print(ob1.search([4,5,6,7,8,0,1,2], 0))

輸入

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

輸出

5

更新於：2020年4月27日

888 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始
廣告