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.

Example 1:

Input: nums = [8, 9, 13, 2, 5]
Output: 2

Example 2:

Input: nums = [24, 26, 3, 7, 10, 18]
Output: 3

Example 3:

Input: nums = [40, 44, 48, 52]
Output: 40

Constraints:

• n == nums.length
• 1 <= n <= 1000
• -1000 <= nums[i] <= 1000
• All values of nums are unique.
• nums was sorted in ascending order and then rotated between 1 and n times.

Solution Breakdown

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 [8,9,13,2,5]: mid=2 (value 13), 13 > nums[4]=5, so low=3; mid=3 (value 2), 2 <= nums[4]=5, so high=3; low and high meet at 3, return nums[3]=2.

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.