Find Minimum in Rotated Sorted Array

Problem

On-call rotation schedules and circular buffers store data that was sorted and then shifted. Given a sorted integer array that was rotated at an unknown pivot, find the minimum element. The array has no duplicate values.

Input: nums = [3, 4, 5, 1, 2]     → 1
Input: nums = [4, 5, 6, 7, 0, 1, 2] → 0
Input: nums = [11, 13, 15, 17]    → 11

Solution

Approach - boundary-finding binary search that converges on the rotation inflection point.

There is no target to match here, so instead you shrink a window down to the single smallest element. Keep low and high, loop while low < high, and at each step compare nums[mid] against the right endpoint nums[high]. The key fact: in a rotated array the minimum is the one place where the order breaks, and nums[high] always sits in the segment that wraps around to that minimum. If nums[mid] > nums[high], then mid lies in the higher left segment and the inflection must be strictly to its right, so low = mid + 1 safely discards mid. If nums[mid] <= nums[high], then mid is in the same segment as the minimum and could itself be the minimum, so high = mid keeps it in play. Comparing against nums[high] rather than nums[low] is what makes this clean - the right side gives an unambiguous read on which segment mid falls in. The window strictly shrinks each step and exits with low == high on the minimum. Trace [3,4,5,1,2]: mid=2 (value 5), 5 > nums[4]=2, so low=3; mid=3 (value 1), 1 <= nums[4]=2, so high=3; low and high meet at 3, return nums[3]=1.

Edge cases - an unrotated array always takes the nums[mid] <= nums[high] branch and converges to index 0; a single element returns immediately; the array is assumed distinct, since duplicates can defeat the mid vs high comparison.

Complexity - O(log n) time, O(1) space - each iteration eliminates one sorted half using only pointers.