Leetcode 153. Find Minimum in Rotated Sorted Array

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)

(1) A[mid] < A[end]：A[mid : end] sorted => min不在A[mid+1 : end]中

搜索A[start : mid]

(2) A[mid] > A[end]：A[start : mid] sorted且又因为该情况下A[end]<A[start] => min不在A[start : mid]中

搜索A[mid+1 : end]

(3) base case：

a. start = end，必然A[start]为min，为搜寻结束条件。

b. start + 1 = end，此时A[mid] = A[start]，而min = min(A[mid], A[end])。而这个条件可以合并到(1)和(2)中。

画图解决，直接明了。

方法二：直接观察发现最小值就是某值比前面的那个数小，就是最小值。也对。当然复杂度是O(n). 还是方法一更好。直接不用方法二，本题考的就是binary search.

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];
    }
}

1.2 九章算法重做本题 2016.01.18

public class Solution {
    public int findMin(int[] nums) {
        if(nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0, end = nums.length-1;
        int target = nums[end];
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(nums[mid] <= target) {
                end = mid;
            }else {
                start = mid;
            }
        }
        if(nums[start] <= target) {
            return nums[start];
        }else {
            return nums[end];
        }
    }
}

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