Blind 75 · Binary Search

Find Minimum in Rotated Sorted Array

Medium

Problem

An ascending array of unique integers was rotated: some prefix was moved to the end, so [1,2,4,5,6,7] might now read [4,5,6,7,1,2]. A rotation of zero is allowed.
Return the smallest element. Your algorithm must run in O(log n) — a linear scan is the answer this problem exists to beat.

Examples

Example 1:
Input: nums = [3,4,5,1,2]
Output: 1

Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0

Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: rotated zero places; still sorted, the first element wins.

Example 4:
Input: nums = [2,1]
Output: 1

Constraints

1 <= nums.length <= 5000
-5000 <= nums[i] <= 5000
All values are unique.

Prerequisites

Binary search — halving a range, and being precise about which half is guaranteed to hold the answer.

How to think about it

1. Binary Search Against the Right End Optimal

Intuition

A rotated sorted array is two sorted runs, and the minimum is exactly where the second begins. Comparing the middle to the RIGHT end says which run the middle is in: greater than the right end means the middle sits in the first run and the drop is further right; otherwise the minimum is at the middle or to its left. Comparing against the LEFT end instead breaks on an unrotated array, which is the trap.

Algorithm

1. Keep a range that is guaranteed to contain the minimum.
2. Compare the middle to the value at the right end.
3. Greater: the minimum is strictly right of the middle.
4. Otherwise: the middle could be the minimum, so keep it and discard the right half.
5. One element left is the answer.

Time & Space

Time O(log n). Space O(1).