<div>
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2]if it was rotated4times.[0,1,2,4,5,6,7]if it was rotated7times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
<pre>Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times. </pre>
Example 2:
<pre>Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times. </pre>
Example 3:
<pre>Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times. </pre>
Constraints:
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000- All the integers of
numsare unique. numsis sorted and rotated between1andntimes.
</div>
算法思路：
二分法
注意事项：
- 如果nums[start] > nums[mid]或nums[mid] > nums[end]都将会是min所在的区间。但是由于无位移数组的min在左边，所以优先判断后半区间nums[mid] > nums[end]，否则若用nums[start] > nums[mid] + else会忽略无位移情况。
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12def findMin(self, nums: List[int]) -> int:
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if nums[mid] > nums[end]:
start = mid
else:
end = mid
if nums[start] < nums[end]:
return nums[start]
else:
return nums[end]
Java代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public int findMin(int[] nums) {
if(nums == null || nums.length == 0)
return -1;
int start = 0, end = nums.length - 1;
while(start + 1 < end) {
int mid = start + (end - start) / 2;
if(nums[start] > nums[end]) {
if (nums[mid] < nums[end])
end = mid;
else
start = mid;
}
else
return nums[start];
}
if(nums[start] < nums[end])
return nums[start];
else
return nums[end];
}
算法分析：
时间复杂度为O(logn)，空间复杂度O(1)
