Find Minimum in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0
分析：
从左向右扫描，扫描到的第一个逆序的位置，肯定是原始数组中第一个元素，时间复杂度O(n)。
不过本题依旧可以用二分查找，最关键的是要判断那个“断层”是在左边还是右边。
- 若A[mid] < A[right]，则区间[mid,right]一定递增，断层一定在左边
- 若A[mid] > A[right]，则区间[left,mid]一定递增，断层一定在右边
- nums[mid] == nums[right]，这种情况不可能发生，因为数组是严格单调递增的，不存在重复元素
思路一：
public class Solution {
public int findMin(int[] nums) {
for(int i = 1; i < nums.length; i++){
if(nums[i] < nums[i-1]){
return nums[i];
}
}
return nums[0];
}
}
时间复杂度o(n)
思路二：
class Solution {
public:
int findMin(vector<int> &num) {
int lo = 0, hi = num.size()-1;
while (lo < hi) {
int mid = ( lo + hi) / 2;
if (num[mid] > num[hi]) lo = mid + 1;
else hi = mid;
}
return num[lo];
}
};
时间复杂度o(log^n)