Find Minimum in Rotated Sorted Array
Medium ArrayBinary Search
Given a sorted array that has been rotated, find the minimum element efficiently. The key insight is recognizing a structural property that lets us eliminate half the search space at each step.
Description
You are given an array of length n which was originally sorted in ascending order. It has been rotated between 1 and n times, where each rotation moves the last element to the front.
For example, the array nums = [1,2,3,4,5,6] might become:
[3,4,5,6,1,2]if rotated4times[1,2,3,4,5,6]if rotated6times (back to original)
All elements in the array are unique. Return the minimum element of this array.
You should write an algorithm that runs in O(log n) time.
Examples
Input: nums = [5,7,9,2,3]
Output: 2
Explanation: The sorted array
[2,3,5,7,9] was rotated 3 positions to the right.Input: nums = [6,8,10,12,1,3,5]
Output: 1
Explanation: The sorted array
[1,3,5,6,8,10,12] was rotated 4 positions.Input: nums = [15,18,21,24]
Output: 15
Explanation: The array was rotated
4 times, returning to its original sorted order.Constraints
- The array length
nsatisfies1 ≤ n ≤ 5000 - Each element
nums[i]is in the range[-5000, 5000] - All elements are unique
- The array is sorted in ascending order and rotated between
1andntimes
Hints
Code Editor