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 rotated4
times.[0,1,2,4,5,6,7]
if it was rotated7
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 between1
andn
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)
};