題目描述:一個原本升序排列的陣列在某個樞紐點旋轉過,找出其中最小值。
解題思路:用二分搜尋縮小範圍。每次比較中間值 nums[mid] 與右端 nums[right]:若 nums[mid] > nums[right],說明最小值在右半段(mid 右側);否則最小值在左半段(含 mid)。持續縮小範圍直到 left == right,此時即為最小值。此方法不需要與 nums[0] 比較,邏輯更清晰。
時間複雜度:O(log n) — 二分搜尋每次縮小一半範圍。
空間複雜度:O(1) — 只用常數個指標變數。
1. Set left = 0, right = n - 1 2. While left < right: a. mid = left + (right - left) / 2 b. If nums[mid] > nums[right]: left = mid + 1 c. Else: right = mid 3. Return nums[left]
線性掃描 O(n):找第一個小於前驅的元素。簡單但未利用排序特性。
與 nums[left] 比較:也可行但非旋轉陣列的邊界情況處理較複雜。與 nums[right] 比較更清晰。