給定一個原本升序排列但經過若干次旋轉的整數陣列
nums（元素不重複），找出陣列中的最小值。要求時間複雜度為O(log n)。
Example:
Input: nums = [3,4,5,1,2] Output: 1
Intuition
TIP
旋轉後的陣列由兩段有序子陣列組成，最小值在「斷點」處。透過比較 mid 與 right 來判斷最小值在哪一半。
- 旋轉陣列形如：
[大, 大, 大, 小, 小, 小]，兩段各自有序 - 如果
nums[mid] > nums[right]，最小值在右半部 - 如果
nums[mid] <= nums[right]，最小值在左半部（含 mid）
Approaches
1. Linear Scan — O(n) / O(1)
- Idea: 遍歷陣列找最小值
- Time:
O(n) - Space:
O(1)
Linear Scan Code
class Solution {
fun findMin(nums: IntArray): Int {
var min = nums[0]
for (num in nums) {
min = minOf(min, num)
}
return min
}
}⭐ 2. Binary Search — O(log n) / O(1)
- Idea: 比較 mid 與 right 來縮小搜尋範圍，找到旋轉的斷點
- Time:
O(log n) - Space:
O(1)
class Solution {
fun findMin(nums: IntArray): Int {
var left = 0
var right = nums.size - 1
while (left < right) {
val mid = left + (right - left) / 2
if (nums[mid] > nums[right]) {
left = mid + 1
} else {
right = mid
}
}
return nums[left]
}
}WARNING
這裡用 left < right（不含等號）配合 right = mid（不是 mid - 1），因為 mid 本身可能就是最小值。如果用 left <= right 會導致無限迴圈。
🔑 Takeaways
- Pattern: 旋轉排序陣列上的二分搜尋
- Key trick: 比較
nums[mid]與nums[right]來判斷最小值的位置。這個技巧也適用於 LC 33（在旋轉陣列中搜尋目標值）