昨天我們解決了「搜尋旋轉排序陣列」，今天我們要挑戰相似題。這兩個題目只有一個微小的差別，但這個差別卻足以讓昨天的程式碼完全失效。

題目連結: 81. Search in Rotated Sorted Array II

題目描述:與第 33 題幾乎一樣，但在這個版本中，陣列 nums 中可能包含重複的元素。請判斷 target 是否存在於陣列中，存在則返回 True，否則返回 False。

Python

問題點:nums = [1, 0, 1, 1, 1]，根據此例子，目前nums[mid]等於陣列第三個元素為1，若沿用昨天的邏輯會

認為左半邊 [left...mid] (即 [1, 0, 1]) 是有序的，但是錯的！斷點 0 就在這個區間裡。

解題思路:

若nums[left] == nums[mid]，則我們慢慢將left+=1，再繼續判斷區間是否有序。

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left = 0
        right = len(nums) -1 
        while left  <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return True
            if nums[mid] == nums[left]:
                left+=1
                continue
            elif nums[mid] >= nums[left]:
                if nums[left] <= target <= nums[mid]:
                    right = mid - 1
                else:
                    left = mid +1
            else:
                if nums[mid]<=target <= nums[right]:
                    left = mid +1
                else:
                    right = mid -1
            
        return False

演算法分析:

• 如果 nums[mid] == target，直接返回 True。
• 如果 nums[left] == nums[mid]，將left += 1，繼續迴圈。
• nums[left] != nums[mid]時，就可以繼續沿用昨天的邏輯來檢查 target 是否在這個有序區間內。

複雜度分析:

• 在大多數情況下，演算法的行為和標準的二分搜尋一樣，都是 O(log n)。

  • 最壞情況：當陣列中充滿了大量的重複元素時，例如 [1, 1, 1, 1, 1, 1, 0, 1]，我們的 left += 1 操作可能會被頻繁觸發，使得演算法退化為線性掃描，時間複雜度變為 O(n)。

• 只使用了常數個額外變數，空間複雜度為 O(1)。

今天就介紹到這邊，有問題都可以留言
下回見!!