在一個可能含有重複元素的旋轉排序陣列中搜尋目標值
target。回傳是否存在。（延伸自 #33，但允許重複元素。）
Example:
Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true
Intuition
TIP
與 #33 相同邏輯，但遇到 nums[left] == nums[mid] == nums[right] 時無法判斷哪邊有序，需要收縮邊界。
- 旋轉排序陣列中，至少有一半是有序的
- 重複元素造成的問題：當
nums[left] == nums[mid] == nums[right]時，無法判斷哪邊有序 - 解法：遇到這種情況就
left++和right--跳過重複
Approaches
1. Linear Scan — O(n) / O(1)
- Idea: 直接遍歷陣列查找
- Time:
O(n) - Space:
O(1)
Linear Scan Code
class Solution {
fun search(nums: IntArray, target: Int): Boolean {
return target in nums
}
}⭐ 2. Binary Search (handle duplicates) — O(log n) / O(1)
- Idea: 二分搜尋，遇到無法判斷的情況就收縮邊界
- Time:
O(log n)平均，O(n)最差（全部重複時） - Space:
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
}
}WARNING
最差情況如 [1,1,1,1,1,1,2,1,1] 搜尋 2，每次只能縮小一格，退化為 O(n)。這是有重複元素的代價。
🔑 Takeaways
- Pattern: 旋轉排序陣列二分搜尋（含重複）
- Key trick: 與 #33 相比只多了一個判斷：
nums[left] == nums[mid] == nums[right]時無法確定有序區間，用left++; right--跳過重複值