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