Find Minimum in Rotated Sorted Array

Suppose an array of length n with distinct values sorted in ascending order is rotated at some pivot unknown to you (e.g. [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Return the minimum element of the array. You must write an O(log n) solution.

• The minimum is the only element that is smaller than its "previous" (the element at the "rotation point"). We can binary search: compare nums[mid] with nums[right] to decide which half contains the minimum.

• If nums[mid] > nums[right], the minimum must be in the right half (mid+1..right] (the array drops after mid). If nums[mid] <= nums[right], the minimum is in the left half [left..mid] (mid could be the minimum). So: if nums[mid] > nums[right], left = mid + 1; else right = mid. Use left < right so we don't skip the minimum; at the end nums[left] is the minimum.
• We compare with right (not left) to correctly handle both sorted and rotated segments.

High-level: Binary search with left < right. If nums[mid] > nums[right], the minimum is to the right: left = mid + 1. Else the minimum is at mid or to the left: right = mid. Return nums[left].

Steps:

1. left = 0, right = nums.length - 1. While left < right: mid = left + (right - left) / 2. If nums[mid] > nums[right], left = mid + 1; else right = mid.
2. Return nums[left].

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

• Find the rotation index (pivot).