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,4,4,5,6,7] might become:
[4,5,6,7,0,1,4]if it was rotated4times.[0,1,4,4,5,6,7]if it was rotated7times.
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 that may contain duplicates, return the minimum element of this array.
You must decrease the overall operation steps as much as possible.
Example 1:
Input: nums = [1,3,5] Output: 1
Example 2:
Input: nums = [2,2,2,0,1] Output: 0
Constraints:
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000numsis sorted and rotated between1andntimes.
Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?
Solutions
This algorithm finds the minimum element in a rotated sorted array using a recursive divide-and-conquer approach. It first checks if the array is already sorted (if nums[0] < nums[last]), in which case it returns the first element. Otherwise, it splits the array in half at the mid point and recursively searches for the minimum: if the left half is rotated (nums[left] > nums[mid]), it searches the left side; if the right half is rotated (nums[mid] > nums[right]), it searches the right side; otherwise, it searches both halves and returns the smaller minimum. The base case returns nums[left] when the range has only one element.
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
if (nums[0] < nums[nums.length - 1]) return nums[0];
return helper(nums, 0, nums.length - 1);
};
const helper = (nums, left, right) => {
if (left >= right) {
return nums[left];
}
const mid = Math.floor((left + right) / 2);
//console.log(left, mid, right);
if (nums[left] > nums[mid]) return helper(nums, left + 1, mid);
if (nums[mid] > nums[right]) return helper(nums, mid + 1, right);
return Math.min(
helper(nums, left, mid),
helper(nums, mid + 1, right),
);
};