Find Minimum in Rotated Sorted Array

You are given an array nums of unique integers that was originally sorted in ascending order, then rotated between 1 and n times.

Rotating [0, 1, 2, 4, 5, 6, 7] four times gives [4, 5, 6, 7, 0, 1, 2]. Return the minimum element of the array.

Input / output

• Input: nums: int[] (all values distinct)
• Output: the smallest value in nums

Examples

1. nums = [3, 4, 5, 1, 2] returns 1.
2. nums = [4, 5, 6, 7, 0, 1, 2] returns 0.
3. nums = [11, 13, 15, 17] returns 11 (no effective rotation).

Constraints

• 1 <= nums.length <= 5000
• -5000 <= nums[i] <= 5000
• All values in nums are distinct.
• nums is a rotation of a strictly ascending array.

Edge cases

• The array may not be rotated at all, so the answer is nums[0].
• A single-element array returns that element.

Target complexity

• Aim for O(log n) time and O(1) extra space.

Hints

1. The array is split into two ascending runs; the minimum is the start of the second run.
2. Compare nums[mid] with nums[right] to decide which half still contains the pivot.

Follow-up How would your approach change if the array could contain duplicate values?