Find Minimum in Rotated Sorted Array
Part of Practice: Rotations & Partitions
A sorted array of unique integers was rotated: some prefix of it was moved to the end. For example [1,2,3,4,5] rotated at position 3 becomes [4,5,1,2,3]. Given the rotated array nums, return its smallest element.
You must do it in O(log n) time, so a linear scan for the minimum is not acceptable. The array may also be rotated zero times (still fully sorted), and it always contains at least one element with all values distinct.
Examples
- Input:
- nums = [3, 4, 5, 1, 2]
- Output:
- 1
The original array [1,2,3,4,5] was rotated 3 times; the minimum is 1.
- Input:
- nums = [4, 5, 6, 7, 0, 1, 2]
- Output:
- 0
- Input:
- nums = [11, 13, 15, 17]
- Output:
- 11
The array was rotated a full cycle (or not at all), so it is still sorted and the first element is the minimum.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.