給定一個旋轉過的升序整數陣列
nums（元素不重複）和一個目標值target，搜尋target是否存在於陣列中。如果存在回傳其索引，否則回傳-1。要求時間複雜度為O(log n)。
Example:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Intuition
TIP
旋轉陣列的左右半部至少有一邊是有序的，先判斷哪半邊有序，再決定 target 是否落在有序的那一半。
- 取 mid 後，
[left, mid]或[mid, right]至少有一段是有序的 - 如果
nums[left] <= nums[mid]，左半部有序：檢查 target 是否在[left, mid)內 - 否則右半部有序：檢查 target 是否在
(mid, 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): Int {
for (i in nums.indices) {
if (nums[i] == target) return i
}
return -1
}
}⭐ 2. Binary Search — O(log n) / O(1)
- Idea: 每次判斷哪半邊有序，再判斷 target 是否在有序的那一半中
- Time:
O(log n) - Space:
O(1)
class Solution {
fun search(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size - 1
while (left <= right) {
val mid = left + (right - left) / 2
if (nums[mid] == target) return mid
// 左半部有序
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 -1
}
}WARNING
判斷左半部有序時用 nums[left] <= nums[mid]（含等號），因為當 left == mid 時（只剩兩個元素），左半部只有一個元素，也算有序。
🔑 Takeaways
- Pattern: 旋轉排序陣列上的二分搜尋
- Key trick: 先判斷哪半邊有序，再決定搜尋方向。這個「判斷有序半邊」的技巧是解決旋轉陣列問題的通用框架