153. Find Minimum in Rotated Sorted Array
假設一個長度為 n 的數組按升序排序後被旋轉了 1 到 n 次。例如，數組 nums = [0,1,2,4,5,6,7] 可能變成：[4,5,6,7,0,1,2] 如果它被旋轉了 4 次。
[0,1,2,4,5,6,7] 如果它被旋轉了 7 次。
注意，將數組 [a[0], a[1], a[2], ..., a[n-1]] 旋轉 1 次會得到數組 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]。
給定一個由唯一元素組成的已排序旋轉數組 nums，返回此數組的最小元素。
你必須設計一個運行時間為 O(log n) 的算法。
範例 ：
輸入: nums = [3,4,5,1,2] 輸出: 1 說明: 原始數組是 [1,2,3,4,5]，旋轉了 3 次。
Python
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
# The minimum is in the right part
left = mid + 1
else:
# The minimum is in the left part including mid
right = mid
return nums[left]
16.97MB, 50ms
C++
#include <vector>
using namespace std;
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
// The minimum is in the right part
left = mid + 1;
} else {
// The minimum is in the left part including mid
right = mid;
}
}
return nums[left];
}
};
12.65MB, 7ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] > nums[right]) {
// The minimum is in the right part
left = mid + 1;
} else {
// The minimum is in the left part including mid
right = mid;
}
}
return nums[left];
};
49.30MB, 78ms
