153. Find Minimum in Rotated Sorted Array.md

153. Find Minimum in Rotated Sorted Array

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));//我们找出左侧的最小值，并和端点值进行比较。
        }
    }
}

Third Time

• Method 1: Binary search

   class Solution {
   	public int findMin(int[] nums) {        
   		return search(nums, 0, nums.length - 1);
   	}
   	private int search(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], search(nums, mid + 1, high));
   		}else{
   			return Math.min(nums[mid], search(nums, low, mid - 1));
   		}
   	}
   }