153. Find Minimum in Rotated Sorted Array

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

Solution

是這題33.-search-in-rotated-sorted-array的基礎題目

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

這題有一個重點, 就是為什麼只能用nums[mid] < nums[hi]來當判斷的conidtion?

其實nums[mid] < nums[lo], 應該也可以推論出pivot point應該在left hand side, 為何執行期會有錯?

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

Input: [3,4,5,1,2] Output: 2 Expected: 1

原因在於, 在searching的過程monotonicity被破壞了, 出現了有序的interval [1,2], 此時如果用原來的邏輯,會一直以為pivot在right side, 所以不同的lo = mid+1, 導致錯誤的結果。

其實理論上因為它的monotonicity在過程中都會被破壞, 都要進行檢查才是, 即使是透過nums[mid] < nums[hi]當作condition也是依樣, 應改成

    public int findMin(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        while(hi > lo){
            int mid = lo + (hi-lo)/2;
            if(nums[lo] <= nums[hi]){ //表示有序, monotonicity已經消失
                return nums[lo];
            }
            if(nums[mid] < nums[lo]){// nums[mid] < nums[hi]也可以
                hi = mid;
            }else{
                lo = mid+1;
            }
        }
        return nums[lo];
    }
}