Suppose a sorted array 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.
方法一：推荐用binary search. O(logn)
方法二：直接观察发现最小值就是某值比前面的那个数小，就是最小值。也对。当然复杂度是O(n). 还是方法一更好。
Java code:
1. Binary search
public class Solution { public int findMin(int[] nums) { int left = 0, right = nums.length-1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < nums[right]){ right = mid; }else{ left = mid+1; } } return nums[left]; } }
2.
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]; } }
Reference:
1. http://bangbingsyb.blogspot.com/2014/11/leecode-find-minimum-in-rotated-sorted.html
Leetcode Find Minimum in Rotated Sorted Array
原文：http://www.cnblogs.com/anne-vista/p/4899735.html