Coding Interview PatternsFind Minimum in Rotated Sorted Array
MediumModified Binary Search
Find Minimum in Rotated Sorted Array
Explanation & Solution
Description
Given a sorted rotated array of unique elements, return the minimum element of the array.
You must write an algorithm that runs in O(log n) time.
Input:nums = [3, 4, 5, 1, 2]
0
3
1
4
2
5
3
1
4
2
Output: 1
Explanation: The original array was [1, 2, 3, 4, 5] rotated 3 times.
Constraints
1 <= nums.length <= 5000-5000 <= nums[i] <= 5000- All values are unique
numsis sorted and rotated between1andntimes
Approach
Modified Binary Search pattern
1. Initialize Pointers
- Set
left = 0andright = nums.length - 1.
2. Binary Search for the Minimum
- Compute
mid = (left + right) >> 1. - Compare
nums[mid]withnums[right].
3. Decide Which Half Contains the Minimum
- If
nums[mid] > nums[right], the rotation point (minimum) must be in the right half →left = mid + 1. - Otherwise, the minimum is at
midor to its left →right = mid.
4. Return the Minimum
- When
left === right, we've found the minimum atnums[left].
🧠 Key Insight
- Comparing
nums[mid]withnums[right](notnums[left]) is crucial. Ifnums[mid] > nums[right], the array is "broken" in the right half, meaning the minimum is there.
Time
O(log n)halves search space each step.Space
O(1).Visualization
Input:
[3, 4, 5, 1, 2]
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
7 steps