Find Minimum in Rotated Sorted Array
FreeBinary searchMedium17 of 75
The problem
A nonempty array of distinct integers was sorted ascending, then rotated zero or more positions. Find its minimum in logarithmic time.
Example
[9, 12, 2, 4, 7] → 2
Need a hint?
Compare the middle element with the rightmost element.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Keep an inclusive search interval. If nums[mid] > nums[right], the minimum lies strictly right of mid, so move left to mid + 1. Otherwise mid may be the minimum, so set right to mid. Return the value when both bounds meet.
Complexity
O(log n) time and O(1) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.