Find Minimum in Rotated Sorted Array – Solution & Complexity

• A rotated ascending array is two sorted runs, e.g. [4,5,6,7] then [0,1,2].
• The minimum value is exactly the first element of the second run (the pivot).
• If the array is not rotated, the pivot is index 0.

• The simplest answer is to scan every element and track the smallest.
• This is O(n) and ignores the sorted structure, but it is a good correctness baseline.

• Compare nums[mid] with nums[right].
• If nums[mid] > nums[right], the pivot is to the right, so move left = mid + 1.
• Otherwise the pivot is at mid or to its left, so move right = mid.
• The loop ends when left == right, pointing at the minimum.

• Keep halving the search window based on the comparison above.
• No mid + 1 on the right side, because mid itself may be the minimum.

Trace nums = [4, 5, 6, 7, 0, 1, 2].

Binary search finds the pivot in O(log n) time and O(1) extra space.