Find Minimum in Rotated Sorted Array
A sorted array of distinct numbers was rotated some number of times. Find its minimum element in O(log n).
A way to picture it
Someone took a neatly sorted bookshelf and moved a chunk from the front to the back. The smallest book sits exactly where the order suddenly drops. Look at the middle book: if it's taller than the last book, the drop must be somewhere to its right.
How to approach it
Compare nums[mid] with nums[right]. If mid is bigger, the minimum is right of mid; otherwise it's at mid or to its left.
Example
Input: {"nums":[3,4,5,1,2]}. Output: 1.
Complexity: O(log n) time and O(1) space. The search range halves every step.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.