Find Minimum in Rotated Sorted Array

Find minimum in rotated sorted array locates the smallest value in a sorted array that has been rotated an unknown number of times. Values are distinct, and the required O(log n) rules out a linear scan. Rotation leaves a specific structure: the array is two sorted runs, with the minimum at the start of the second. That element is also the single point where an element is smaller than its predecessor — the rotation point. Ordinary binary search compares against a target, but there is no target here. The comparison that works instead is between mid and the right end: - If nums[mid] > nums[right], the rotation point lies to the right of mid; otherwise mid could itself be the minimum. The reasoning is direct. A middle element larger than the rightmost means mid sits in the first, higher run, so the minimum must be further right — move left = mid + 1, safely excluding mid. Otherwise mid is in the second run and might be the minimum itself, so move right = mid, keeping it as a candidate. Comparing against nums[left] instead is the classic error. It cannot distinguish a rotated array from an unrotated one, because in both cases the middle can exceed the left element. The loop runs while left < right, converging when the two meet. No separate check for an unrotated array is needed: if the array was never rotated, every comparison sends the search left and it lands on index 0 correctly. With duplicates allowed the comparison breaks down, and the worst case degrades to O(n) — that is Find Minimum in Rotated Sorted Array II.

Compare nums[mid] to nums[hi], never to nums[lo]. If the midpoint exceeds the right end, the rotation point lies strictly to the right; otherwise the minimum is at or left of mid. Anchoring on the right end is what makes the two cases unambiguous.