Find Minimum in Rotated Sorted Array

Problem

An array of distinct integers, originally sorted in ascending order, has been rotated by some amount between 0 and n - 1 positions. Return the smallest element in logarithmic time.

• nums has between 1 and 20,000 elements, all distinct.
• Values are integers between -100,000 and 100,000.
• A rotation of 0 (the array is already sorted) is allowed.

Examples

• nums = [8, 10, 14, 3, 5] → 3. The original array [3, 5, 8, 10, 14] was rotated by 3.
• nums = [20, 25, 30, 1, 6, 9, 12] → 1.
• nums = [2, 6, 7, 9] → 2. No rotation; the first element is the minimum.

Hints

1. The minimum is the only element smaller than its left neighbour. Scanning for it is O(n); how could you jump there?
2. Compare nums[mid] with the last element of the current window. What does each outcome tell you about where the minimum is?
3. Binary search: if nums[mid] > nums[hi] the drop is to the right of mid, otherwise it is at mid or to the left.