81. Search In Rotated Sorted Array II

Medium
Description

在一個可能含有重複元素的旋轉排序陣列中搜尋目標值 target。回傳是否存在。（延伸自 #33，但允許重複元素。）

Example:

Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true

Intuition#

與 #33 相同邏輯，但遇到 nums[left] == nums[mid] == nums[right] 時無法判斷哪邊有序，需要收縮邊界。

  • 旋轉排序陣列中，至少有一半是有序的
  • 重複元素造成的問題：當 nums[left] == nums[mid] == nums[right] 時，無法判斷哪邊有序
  • 解法：遇到這種情況就 left++ 和 right-- 跳過重複

Approaches#

1: Linear Scan#

  • 概念: 直接遍歷陣列查找
  • 時間複雜度: O(n)
  • 空間複雜度: O(1)
Linear Scan 程式碼
class Solution {
    fun search(nums: IntArray, target: Int): Boolean {
        return target in nums
    }
}

⭐2: Binary Search（處理重複）#

  • 概念: 二分搜尋，遇到無法判斷的情況就收縮邊界
  • 時間複雜度: O(log n) 平均，O(n) 最差（全部重複時）
  • 空間複雜度: O(1)
class Solution {
    fun search(nums: IntArray, target: Int): Boolean {
        var left = 0
        var right = nums.size - 1
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (nums[mid] == target) return true

            // 無法判斷哪邊有序，收縮邊界
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++
                right--
            } else if (nums[left] <= nums[mid]) {
                // 左半部有序
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            } else {
                // 右半部有序
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1
                } else {
                    right = mid - 1
                }
            }
        }
        return false
    }
}

最差情況如 [1,1,1,1,1,1,2,1,1] 搜尋 2，每次只能縮小一格，退化為 O(n)。這是有重複元素的代價。

🔑 Takeaways#

  • Pattern: 旋轉排序陣列二分搜尋（含重複）
  • 關鍵技巧: 與 #33 相比只多了一個判斷：nums[left] == nums[mid] == nums[right] 時無法確定有序區間，用 left++; right-- 跳過重複值