解題說明
Search in Rotated Sorted Array
題目描述：在旋轉後的升序陣列中搜尋目標值 target，回傳其索引，若不存在回傳 -1。
解題思路：雖然陣列旋轉過，但每次二分後，左半或右半中必有一段是嚴格有序的。用 nums[left] <= nums[mid] 判斷左半是否有序：若有序且 target 在其範圍內，縮小至左半；否則縮小至右半。對右半同理。這樣每次都能安全地排除一半範圍。
C++ 解法
複雜度分析
時間複雜度：O(log n) — 改良版二分搜尋，每次縮小一半。
空間複雜度：O(1) — 只用常數個指標。
虛擬碼
1. Set left = 0, right = n - 1
2. While left <= right:
a. mid = midpoint
b. If nums[mid] == target: return mid
c. If left half [left..mid] is sorted (nums[left] <= nums[mid]):
- If target in [nums[left], nums[mid]): right = mid - 1
- Else: left = mid + 1
d. Else (right half [mid..right] is sorted):
- If target in (nums[mid], nums[right]]: left = mid + 1
- Else: right = mid - 1
3. Return -1其他解法
先找樞紐再二分：首先定位旋轉點 O(log n)，再決定哪一半包含目標並進行標準二分搜尋。兩次掃描但總體複雜度相同。
線性掃描 O(n)：簡單但不符合排序陣列的目的。
延伸思考
- 若陣列包含重複 (Search in Rotated Sorted Array II) 呢？
- 陣列旋轉了多少次？
- 若有多個旋轉點呢？