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.