Leetcode Rotated Sorted Array related questions

Yaowen

2020-05-17

Algorithm, Leetcode, Java, Binary Search

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 2	Input: [4,5,6,7,0,1,2] Output: 0

Follow up:

Can you think of an algorithm which has O(logN) search complexity?

Notes

This is a binary search question.

Key code:

private int helper(int[] nums, int low, int high){
        if(low == high){
            return nums[low];
        }
        
        int mid = (low + high) / 2;
        
        if(nums[mid] > nums[high]){
            return helper(nums, mid+1, high);
        } else {
            return helper(nums, low, mid);
        }
}

Explanation:

[4,5,6,7,0,1,2] ——-> 7 > 2, true ——–> [0,1,2] ——– 1 > 2, false ——–> [0,1] ——-> [0]

[6,7,0,1,2,4,5] ——-> 1 > 5, false ——-> [6,7,0,1] —–> 7 > 1, true ——–> [0,1] ——-> [0]

Note: can not use

if(nums[mid] > nums[low]){
           return helper(nums, mid+1, high);
       } else {
           return helper(nums, low, mid);
    }

Explanation:

[4,5,6,7,0,1,2] ——-> 7 > 4, true ——–> [0,1,2] ——-> 1 > 0, true ——–> [1,2] ——-> [2]

[6,7,0,1,2,4,5] ——-> 1 > 6, false ——-> [6,7,0,1] —–> 7 > 6, true ——–> [0,1] ——-> [0]

Overall explanation:

[4,5,6,7] and [0,1,2] are both ascending order, which means nums[high] is great than nums[low], unless the following situation: [7,0,1,2], nums[3] is less than nums[0].