Find Minimum in Rotated Sorted Array

Problem A sorted array of distinct integers was rotated at an unknown pivot. Find the minimum element in O(log n).

Input / Output

• Input: int array nums (rotated sorted). Output: the minimum value.

Constraints

• n up to 5000; O(log n) required; know how duplicates degrade the bound.

Example

• [3,4,5,1,2] → 1; [11,13,15,17] → 11 (not rotated).

Expected approach

• Binary search comparing mid against the RIGHT end: nums[mid] > nums[hi] → minimum is right of mid (lo = mid+1); else it's at mid or left (hi = mid). Terminates with lo == hi at the minimum. Comparing against the left end fails on non-rotated arrays — a classic probe. With duplicates (variant II): nums[mid] == nums[hi] → hi-- (worst case O(n)). O(log n)/O(1).