Find Minimum in Rotated Sorted Array
How to find the smallest value — the rotation point — in a sorted-then-rotated list, in O(log n), without ever comparing to a target.
The job
A sorted list was rotated by some unknown amount. Find its smallest value — the exact point where a bigger number sits right before a smaller one.
The obvious way
Scan every value and keep the smallest one seen.A list of 1,000,000 can cost 1,000,000 checks.
The idea
Compare the middle value to the value at `hi`. If it is BIGGER, the rotation point must be somewhere to the right — mid can be dropped. If it is smaller or equal, the rotation point is at mid or to its left — so keep mid, since it might be the answer itself, and drop everything strictly after it.
Think of it like this. Feeling along a rope for the one knot where the strand suddenly gets thinner. At any point you grab, comparing that spot's thickness to the very end tells you which direction the knot is in — and you never need to feel the whole rope to find it.
Halving toward the rotation point
7 numbers — sorted, then rotated at some unknown point. Find the smallest one.
def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]This run
The minimum is 0, at index 4 — found in 3 looksinstead of scanning all 7.
Why mid sometimes survives
Compare to hi, not to a target
There is no value being searched for — the comparison is `nums[mid]` against `nums[hi]`, which is enough to tell which side the rotation point is on.
mid can BE the answer
Ordinary binary search always discards mid once it is checked and not equal to the target. Here, when the left side keeps mid, it is because mid itself might be the minimum — so `hi` moves to `mid`, not `mid - 1`.
The loop condition changed too
lo < hi instead of lo <= hi — the loop stops the moment the window holds exactly one value, and that value is guaranteed to be the answer.
How to spot this shape
The tell: You need a specific INDEX or boundary in a rotated or otherwise "broken-sorted" sequence, and comparing `mid` to one fixed end (not to a target) tells you which side it is on.
Reach for it when
- The problem asks for the rotation point, a boundary, or "where does the pattern break."
- There is no target value to search for — the answer is a property of the array itself.
- A comparison between mid and one array endpoint is enough to halve the search space.
- The array is explicitly described as sorted-then-rotated.
Not this when
- You are searching for a specific target value — that is 33, not this.
- Duplicates can make nums[mid] == nums[hi], hiding which side is smaller.
- The array has more than one rotation or is not sorted before rotating.
Practice
6 problemsThe lesson, exactly. Compare mid to hi, and keep mid in the window whenever it might still be the minimum.
Duplicates can make nums[mid] == nums[hi], which hides which side the minimum is on — fall back to shrinking hi by one and retry.
The rotation point this lesson finds is exactly the pivot that problem's "which half is sorted" test relies on — its own lesson here too.
The same "keep mid, compare to a neighbor" halving shape, hunting a local maximum instead of the rotation point — its own lesson here too.
A different invariant (pair-index parity before and after the lone element) drives the same halve-and-keep-or-discard shape.
Binary search a PARTITION point instead of a value — a further generalization of "halve based on a property of mid," not a rotation problem at all.