Find Minimum in Rotated Sorted Array

Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

 

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

 

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

Solution(javascript)

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    // let min = nums[0];
    // nums.sort((a,b) => a -b);
    // if (nums[0] < min) return nums[0]
    // return min;
    // Binary Search
    var left = 0,
        right = nums.length - 1
    
    while (left < right){
        var mid = Math.floor((left + right)/2)
        //For an un-rotated sorted array, we can easily understand that there can never be a case where nums[mid] would ever be greater than nums[right]. However, this condition can happen in a rotated array if the mid pointer is residing on the left side of the rotated array. Once we know that the mid pointer is at the left side of the array, we can start to cut down our search to only the right side since we know that the minimum value can never be in the left side. Hence, we update the left pointer to be mid + 1, indicating that we are now searching the right side.


        if (nums[mid] > nums[right]) left = mid + 1
        // This condition will tell us that the subarray that we are currently searching is now a properly sorted array which is un-rotated. To get the minimum value of this subarray, we simply have to keep adjusting the right pointer to the left by setting the mid pointer as the right pointer, cutting down our serach to only the left half of this subarray. Eventually, we will reach the left most element of this subarray.

        else right = mid
    }
    return nums[left]
    //Time = O(logn)
};