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.
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.
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
Common pitfalls
Comparing against nums[lo]
if nums[mid] > nums[lo]:
if nums[mid] > nums[hi]:
On an unrotated array nums[mid] > nums[lo] holds while the minimum is at lo, sending the search the wrong way. The right-end comparison is unambiguous in both the rotated and unrotated cases.
Excluding mid when searching left
else:
hi = mid - 1else:
hi = midmid itself can be the minimum — on [3, 4, 5, 1, 2] the search lands on index 3 exactly. Dropping it loses the answer and returns a neighbouring value.
Using lo <= hi as the loop condition
while lo <= hi:
while lo < hi:
With hi = mid the range never empties, so lo <= hi spins forever once they converge. The lo < hi form terminates exactly when the two meet on the answer.
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.