解題說明
Search in Rotated Sorted Array II
題目描述：
給定一個可能包含重複元素的排序陣列，在某個未知的旋轉點處被旋轉後，判斷目標值 target 是否存在於陣列中。
解題思路： 此題是 LeetCode 33 的延伸，加入了重複元素。核心仍是二分搜尋，但重複元素會造成無法判斷哪半邊有序的情況。
- 取中間值
nums[mid]，若等於 target 則直接回傳 true。 - 若
nums[left] == nums[mid] == nums[right]，無法判斷哪邊有序，只能同時收縮left++和right--。 - 若左半段有序（
nums[left] <= nums[mid]），檢查 target 是否落在[nums[left], nums[mid])內，是則搜右半段，否則搜左半段。 - 否則右半段有序，類似地判斷 target 落在哪半段。
重複元素使最壞情況退化至 O(n)，但平均情況仍為 O(log n)。
C++ 解法
複雜度分析
時間複雜度：O(log n) 平均，O(n) 最壞情況 — 當所有元素相同時，每次只能收縮一個邊界。
空間複雜度：O(1) — 只使用常數個指標變數。
虛擬碼
1. Initialize left = 0, right = n - 1
2. While left <= right:
a. Compute mid = left + (right - left) / 2
b. If nums[mid] == target, return true
c. If nums[left] == nums[mid] == nums[right]: left++, right-- (skip duplicates)
d. Else if nums[left] <= nums[mid] (left half sorted):
- If target in [nums[left], nums[mid)): right = mid - 1
- Else: left = mid + 1
e. Else (right half sorted):
- If target in (nums[mid], nums[right]]: left = mid + 1
- Else: right = mid - 1
3. Return false其他解法
線性掃描 O(n)：直接遍歷整個陣列尋找 target。實作最簡單，但放棄了二分搜尋的優勢。在最壞情況下與二分法效率相同，但平均情況遠不如二分法。
去重後二分搜尋：先用 O(n) 去除重複元素，再用標準旋轉陣列二分搜尋。時間仍為 O(n)（去重步驟），但邏輯分離更清晰，適合理解但不適合面試最佳解。
延伸思考
- 若陣列不含重複元素，時間複雜度能保證 O(log n) 嗎？為什麼重複元素破壞了這個保證？
- 在最壞情況（如 [1,1,1,1,1,1,2,1,1]）下，能否設計比 O(n) 更快的算法？
- 如何修改此算法來找到 target 的索引而非僅判斷存在性？