Find Minimum in Rotated Sorted Array
Find the minimum of a sorted array of distinct values that was rotated at an unknown pivot.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Binary search against the right end: if nums[mid] > nums[right] the minimum is to the right of mid, otherwise it is at mid or to its left.
Pattern: Binary search. Discard half of the remaining search space with every comparison.
Complexity
| Measure | Bound |
|---|---|
| Time | O(log n) |
| Extra space | O(1) |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.