Find Minimum in Rotated Sorted Array: Binary Search Without a Target
Solve Find Minimum in Rotated Sorted Array in O(log n) with pivot binary search — compare mid to the right boundary. Code, walkthrough, and pitfalls.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Every binary search problem you've solved so far handed you a target: find this number, guess this value. Find Minimum in Rotated Sorted Array takes the target away. There is no number to look for — only a structural feature to locate: the rotation point where a sorted array was cut and its two halves swapped.
That shift is the whole lesson. Once you can binary search for a property boundary instead of a value, an entire tier of medium problems opens up — rotated-array search, peak finding, boundary hunting. And the core loop is four lines long.
The catch: those four lines are easy to get subtly wrong. Compare against the wrong end of the array and non-rotated inputs break; shrink the window by one index too many and you skip the answer. Every comparison here has a reason.
The problem
An array sorted in ascending order has been rotated between 1 and n times. [0,1,2,4,5,6,7] rotated 4 times becomes [4,5,6,7,0,1,2]. Given the rotated array nums of unique elements, return its minimum — in O(log n) time.
Input: nums = [3, 4, 5, 1, 2]
Output: 1 // original array [1,2,3,4,5], rotated 3 timesTwo facts in the setup do the heavy lifting:
- Rotation cuts one sorted array into two sorted blocks: a left block of larger values (
3,4,5) and a right block of smaller ones (1,2). The minimum is the first element of the right block — the pivot. - Elements are unique, so every comparison gives an unambiguous answer. (Duplicates are a separate, harder problem.)
The brute force baseline
The minimum of any array is one linear scan away:
function findMin(nums) {
let min = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] < min) min = nums[i];
}
return min;
}This is O(n), and on LeetCode's small inputs it even passes. But it treats nums as an unordered bag of numbers, throwing away the one thing that makes this problem interesting: the array is almost sorted. The statement demands O(log n) because the interviewer wants to see you exploit that structure — Math.min(...nums) answers a different, easier question.
The key insight: compare mid to the right boundary
This is pivot binary search. At every step, ask: is the window from mid to right sorted? One comparison answers it.
- If
nums[mid] > nums[right], the window is not sorted — somewhere betweenmidandright, values drop. That drop is the rotation point, so the minimum lives strictly to the right ofmid. Discardmidand everything left of it:left = mid + 1. - If
nums[mid] < nums[right], the stretch frommidtorightis sorted, and its smallest element isnums[mid]itself. The overall minimum is atmidor somewhere to its left. Keepmidin play:right = mid.
Either way, the window halves while maintaining one loop invariant: the minimum is always inside [left, right]. When the window collapses to a single index, that index is the minimum.
Notice what's missing: no target, no equality check, no early return. You never "find" anything mid-loop — you squeeze the window until only the answer remains.
The optimal solution
function findMin(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > nums[right]) {
left = mid + 1; // drop is right of mid — mid can't be the min
} else {
right = mid; // mid..right is sorted — mid might be the min
}
}
return nums[left];
}Three deliberate choices, each load-bearing:
while (left < right), not<=. The loop's job is to shrink the window to one element, then stop. With<=andright = mid, the caseleft === rightwould loop forever.- Asymmetric updates.
left = mid + 1is safe because a mid greater than the right boundary can never be the minimum. Butright = mid— notmid - 1— because when the right window is sorted,nums[mid]is still a candidate. Cut it and you can cut the answer. - Return
nums[left], the value at the converged index.leftitself is the pivot index — useful trivia, wrong answer.
Step through it interactively to watch the window collapse comparison by comparison on your own inputs.
Walkthrough: nums = [3, 4, 5, 1, 2]
| Step | left | right | mid | nums[mid] | nums[right] | Decision |
|---|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 5 | 2 | 5 > 2 → drop is to the right → left = 3 |
| 2 | 3 | 4 | 3 | 1 | 2 | 1 < 2 → mid..right sorted → right = 3 |
| 3 | 3 | 3 | — | — | — | left === right → return nums[3] = 1 |
Step 2 is the one to internalize. nums[3] = 1 is the actual minimum, and the algorithm doesn't know that yet — it only knows the window [3, 4] is sorted, so the smallest candidate is at mid. Setting right = mid keeps index 3 alive; right = mid - 1 would have thrown the answer away and returned 2.
Run the same trace on a non-rotated input like [1, 2, 3, 4, 5]: every comparison finds nums[mid] < nums[right], so right walks down to 0 and the loop returns nums[0] = 1. The right-boundary comparison handles rotated and non-rotated arrays with the same four lines.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Linear scan | O(n) | O(1) | touches every element, ignores the sorted structure |
Scan for the drop (nums[i] < nums[i-1]) | O(n) | O(1) | still linear — finds the pivot the slow way |
| Pivot binary search | O(log n) | O(1) | one comparison halves the window every iteration |
A 1,000,000-element array resolves in about 20 comparisons; the only state is two pointers and a mid index.
Common mistakes
- Comparing
nums[mid]withnums[left]instead ofnums[right]. On a non-rotated array like[1, 2, 3, 4, 5],nums[mid] > nums[left]is true, which sends you right — away from the minimum sitting at index 0. The left boundary can't distinguish "sorted" from "rotated with the pivot to my right"; the right boundary can. - Setting
right = mid - 1. Whennums[mid] < nums[right], mid is a live candidate for the minimum. Excluding it breaks the invariant and returns a neighbor of the answer on inputs like[3, 4, 5, 1, 2]. - Looping with
left <= right. Combined withright = mid, the window can stop shrinking and the loop never exits.left < rightplus the asymmetric updates guarantees progress every iteration. - Returning
leftinstead ofnums[left]. The problem asks for the minimum value. The converged index is the rotation pivot — a great thing to know for the follow-up problem, but not the answer here. - Assuming the code handles duplicates. With repeated values,
nums[mid] === nums[right]tells you nothing about which side holds the pivot. That variant (LeetCode 154) needs an extraright--shrink step and degrades to O(n) worst case.
Where this pattern shows up next
Find Minimum is the bridge between vanilla binary search and binary-search-on-structure:
- Binary Search — the classic target-based loop this problem deliberately breaks away from.
- Guess Number Higher or Lower — target-based search where the comparison comes from an oracle instead of an array read.
- Sqrt(x) — binary search over an answer space rather than an array, the other classic "no explicit target" setup.
- Search in Rotated Sorted Array — the direct sequel: reuse the sorted-half reasoning from this problem, but now with a target to find inside one of the halves.
FAQ
Why compare nums[mid] with nums[right] instead of nums[left]?
Because the right boundary gives an unambiguous signal in both possible states of the array. If nums[mid] > nums[right], the window definitely contains the rotation drop and the minimum is right of mid. If nums[mid] < nums[right], the stretch from mid to right is definitely sorted and the minimum is at mid or left of it. Comparing with nums[left] fails on non-rotated input: in [1, 2, 3, 4, 5], nums[mid] > nums[left] holds even though the minimum is at the far left, so the search walks away from the answer.
Why is the update left = mid + 1 but right = mid?
The asymmetry mirrors what each comparison proves. When nums[mid] > nums[right], mid is provably not the minimum — something smaller exists to its right — so it's safe to exclude mid with left = mid + 1. When nums[mid] < nums[right], mid might be the minimum, so right = mid keeps it inside the window. Using right = mid - 1 can discard the answer itself.
What is the time complexity of Find Minimum in Rotated Sorted Array?
O(log n) time and O(1) space with pivot binary search: each iteration performs one comparison and halves the search window, so a million-element array resolves in roughly 20 steps. A linear scan is O(n), which passes small test cases but ignores the sorted structure the problem explicitly asks you to exploit.
Does the algorithm work if the array is not rotated?
Yes, with no special-casing. On a fully sorted array, nums[mid] < nums[right] is true at every step, so right keeps moving down to mid until the window collapses at index 0 — the true minimum. This uniform behavior is exactly why the comparison targets the right boundary; a left-boundary comparison needs the array to actually be rotated to work.
What changes when the array contains duplicates?
The comparison loses information: when nums[mid] === nums[right], the pivot could be on either side, and neither half can be safely discarded. The standard fix (LeetCode 154, Find Minimum in Rotated Sorted Array II) shrinks the window by one with right-- in that case, which is correct but drops the worst-case time to O(n) — for example on an array of all-identical values.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.