题目：

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.

链接： 

题解：

rotated sorted array找最小值。 跟rotated sorted array找target很类似，但更简单一些。还是用二分查找。

Time Complexity - O(logn)，Space Complexity - O(1)。注意一开始的条件就可以判断nums[lo] > nums[hi]，假如nums[lo] < nums[hi]的话那数组就是sorted。

public class Solution {    public int findMin(int[] nums) {        if(nums == null || nums.length == 0)            return Integer.MIN_VALUE;                int lo = 0, hi = nums.length - 1;                while(lo < hi && nums[lo] > nums[hi] ) {            int mid = lo + (hi - lo) / 2;            if(nums[mid] < nums[hi]) {                hi = mid;            } else                lo = mid + 1;        }                return nums[lo];    }}

 

二刷:

方法还是Binary Search。 注意当nums[lo] <= nums[hi]的时候，我们可以直接返回nums[lo]。 也可以把这个if 条件挪到while循环的判断语句中。二分查找的条件是，先求出mid，当nums[mid] > nums[hi]的时候，说明最小值在mid右边，我们可以更新lo = mid + 1。否则，这个最小值可能在mid及mid左边，我们更新hi = mid。

Java:

public class Solution {    public int findMin(int[] nums) {        if (nums == null || nums.length == 0) return Integer.MIN_VALUE;        int lo = 0, hi = nums.length - 1;        while (lo <= hi) {            if (nums[lo] <= nums[hi]) return nums[lo];            int mid = lo + (hi - lo) / 2;            if (nums[mid] > nums[hi]) lo = mid + 1;            else hi = mid;        }        return nums[lo];    }}

 

Update:

public class Solution {    public int findMin(int[] nums) {        if (nums == null || nums.length == 0) return Integer.MIN_VALUE;        int lo = 0, hi = nums.length - 1;        while (lo <= hi && nums[lo] > nums[hi]) {            int mid = lo + (hi - lo) / 2;            if (nums[mid] > nums[hi]) lo = mid + 1;            else hi = mid;        }        return nums[lo];    }}

 

三刷：

Java:

public class Solution {    public int findMin(int[] nums) {        if (nums == null || nums.length == 0) return Integer.MAX_VALUE;        int lo = 0, hi = nums.length - 1;        while (lo < hi && nums[lo] > nums[hi]) {            int mid = lo + (hi - lo) / 2;            if (nums[lo] <= nums[mid]) lo = mid + 1;            else hi = mid;        }        return nums[lo];    }}

 

 

Reference：