Question

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

Thinking:

  • Method: 至少有一半是in order的。
class Solution {
    public int findMin(int[] nums) {
        if(nums.length == 1) return nums[0];
        int len = nums.length;
        int mid = nums[len / 2];
        if(mid > nums[0]){  // left part in order.
            for(int i = len / 2 + 1; i < len; i++){
                if(nums[i] < nums[i - 1]) return nums[i];
            }
            return nums[0];
        }else{
            for(int i = 0; i < len / 2; i++){
                if(nums[i + 1] < nums[i]) return nums[i + 1];
            }
            return nums[len / 2];
        }
    }
}

二刷

  1. Method 1： 因为一定有一半是顺序的，所以我们通过判断中间值和两端的某个值来确定哪一半是顺序的，然后找出另一半中的最小值并和另一端的端点值进行比较，从而找出最小值。算法复杂度是O（N）。 
    class Solution {
 public int findMin(int[] nums) {
     if(nums.length == 1) return nums[0];
     int mid = nums.length / 2;
     if(nums[mid] > nums[0]){
         for(int i = mid + 1; i < nums.length; i++)
             if(nums[i] < nums[i - 1]) return nums[i];
         return nums[0];
     }else{
         for(int i = 1; i <= mid; i++)
             if(nums[i] < nums[i - 1]) return nums[i];
         return nums[mid];
     }
 }
}
  2. 使用二分法， log(N) 
    class Solution {
 public int findMin(int[] nums) {
     if(nums.length == 1) return nums[0];
     int low = 0, high = nums.length - 1;
     return find(nums, low, high);
 }
 private int find(int[] nums, int low, int high){
     if(low >= high) return nums[low];   // 退出循环的条件。定位到了某个值，并且当前数组中只有这一个值，必定是最小的。
     int mid = low + (high - low) / 2;
     if(nums[mid] > nums[low]){ //左侧是顺序的 
         return Math.min(nums[low], find(nums, mid + 1, high));  //此时左侧是顺序的，我们在右侧中找出最小值，并和左侧端点进行比较。
     }else{  //右侧是顺序的
         return Math.min(nums[mid], find(nums, low + 1, mid));//我们找出左侧的最小值，并和端点值进行比较。
     }
 }
}