Find Minimum in Rotated Sorted Array
A sorted array of distinct values has been rotated some unknown number of times. Return its minimum element in O(log n).
Open on LeetCode ↗Intuition
A rotated sorted array is two ascending runs stuck together, and the minimum sits exactly at the seam where the higher run drops into the lower one. The trick is finding a comparison that reliably tells you which side of the seam the midpoint is on. Comparing nums[mid] against nums[hi] does it: if the midpoint is larger than the last element, the seam has not been passed yet and lies strictly to the right; otherwise the stretch from mid to the end is properly sorted, so mid is already in the lower run and the minimum is at mid or before it.
Approach
Picture the two runs
Take [4,5,6,7,0,1,2]. It is [4,5,6,7] followed by [0,1,2], both ascending, with a single drop between 7 and 0. The minimum is the first element of the second run. Every rotated array has exactly this shape — including the unrotated case, which is just one run with an empty second.
Compare against the right end, not the left
This is the choice that matters. If nums[mid] > nums[hi], then mid sits in the higher run — everything from mid to hi cannot be sorted, so the drop is somewhere after mid. Move lo = mid + 1, safely excluding mid since it is definitely not the minimum. If nums[mid] <= nums[hi], then mid through hi is a clean ascending stretch, so mid belongs to the lower run and the minimum is at mid or to its left. Move hi = mid, keeping mid because it might be the answer.
Why comparing against nums[lo] fails
The tempting alternative — comparing nums[mid] with nums[lo] — breaks on a non-rotated array like [1,2,3,4], where mid is greater than lo and the rule wrongly sends the search right. Anchoring on hi handles the unrotated case correctly with no special branch, because a fully sorted array always takes the nums[mid] <= nums[hi] path and converges on index 0. Loop while lo < hi and return nums[lo] when they meet.
Solution & live demo
Edge cases
Every comparison takes the nums[mid] <= nums[hi] branch and hi walks down to 0, returning the first element. This is precisely why the comparison anchors on hi.
The loop never executes and the single element is returned.
The minimum is at index 1 in a two-element view; the standard rule finds it without special handling.
This variant (LC 154) breaks the guarantee: when nums[mid] == nums[hi] neither side can be ruled out. The fix is to decrement hi by one, degrading the worst case to O(n). The distinct-values version here has no such problem.