Q32: Find Minimum in Rotated Sorted Array
Given a sorted array of unique elements rotated between 1 and $n$ times, find the minimum element in $O(\log n)$ time using Binary Search.
Rotated Array Binary Search Minimum
function findMin(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
console.log(findMin([3,4,5,1,2])); // 1💡 If
nums[mid] > nums[right], pivot point and minimum element must be right of mid (left = mid + 1). Otherwise minimum is at mid or left of mid (right = mid).Key Takeaways
- Compare
nums[mid]againstnums[right]to determine which half is sorted. - If
nums[mid] > nums[right], minimum lies strictly in the right partition.
Knowledge Check
Why is `right = mid` used instead of `right = mid - 1` when `nums[mid] <= nums[right]`?