C++ 中旋轉排序陣列 II 的搜尋

假設我們有一個按升序排序的陣列。該陣列在某個未知的樞軸點旋轉。例如，如果陣列像 [0,0,1,2,2,5,6]，它可能會變成 [2,5,6,0,0,1,2]。我們有一個目標值需要搜尋。如果該值在陣列中找到，則返回 true，否則返回 false。所以如果陣列像 [2,5,6,0,0,1,2]，目標是 0，則輸出將是 0

讓我們看看步驟 -

• 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):
      """
      :type nums: List[int]
      :type target: int
      :rtype: int
      """
      low = 0
      high = len(nums)
      while low<high:
         mid = low + (high-low)//2
         print(mid)
      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

輸入

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

輸出

true

Arnab Chakraborty

更新於: 2020-02-03

176 次瀏覽

啟動你的 職業生涯

透過完成課程獲得認證

開始學習