Find Minimum in Rotated Sorted Array
A sorted array was cut in two and the halves swapped. Find its smallest number in O(log n) by binary searching for the cut.
- Binary search on a rotated array
- Compare with the right end
Before this, know: Binary search (lo, hi, mid), Sorted order
Start with a sorted array of different numbers, like [0, 1, 2, 4, 5, 6, 7].
Rotating it means taking some items off the front and sticking them on the
back, in the same order. Rotate it 4 times and you get [4, 5, 6, 7, 0, 1, 2].
You’re given the rotated array (you don’t know how many times it was rotated)
and must return its smallest number. Here, that’s 0.
Draw the numbers as bars and the shape is easy to see: a rising run, a sudden drop, and another rising run. We’ll call the drop the cliff. The minimum is always the first bar after the cliff.
Rules that matter:
- All numbers are different.
- The array may have been rotated
ntimes, which puts it back in sorted order:[11, 13, 15, 17]. Then there’s no cliff and the minimum is the first item. - You must run in O(log n) time, so reading every number isn’t allowed.
Why compare nums[mid] with nums[hi] (the right end of the range)? Because
inside one rising run, values only go up. So:
nums[mid] > nums[hi]: something bigger comes before something smaller. That can only happen if the cliff is between them. The minimum is to the right ofmid.nums[mid] < nums[hi]: frommidtohieverything rises with no cliff. Nothing right ofmidis smaller thannums[mid]. The minimum is atmidor to its left.
Pause and think
1 < 4, so mid..hi rises with no cliff: nothing to the right of mid can be
smaller than 1. Throw the right side away: hi = mid.
But don’t throw away mid itself: it might be the minimum (here it is!).
That’s why this problem uses hi = mid, not hi = mid − 1.
Look at every number and remember the smallest.
Brute force: look at every number
nums = [4, 5, 6, 7, 0, 1, 2]
- 40
- 51
- 62
- 73
- 04
- 15
- 26
- smallest
- 4
- Looking at
- Smallest so far
- Already seen
4: smallest so far is still 4.
Which line is running?
function findMin(nums) { let smallest = nums[0]; for (const x of nums) {Running now: if (x < smallest) smallest = x; } return smallest;}Brute force: scan for the smallest
function findMin(nums) { let smallest = nums[0]; for (const x of nums) { if (x < smallest) smallest = x; } return smallest;}def find_min(nums): smallest = nums[0] for x in nums: if x < smallest: smallest = x return smallestIt reads all n numbers: 7 looks for 7 items, 5,000 looks for 5,000 items. That’s
O(n). It’s correct, but the problem
asks for O(log n), about 13 looks for
5,000 items, and the scan ignores that the array is almost sorted.
A rotated sorted array isn’t sorted, but it’s sorted in two pieces, and one
comparison with the right end tells you which piece mid is in. That’s enough
to throw away half the range every round.
Pattern
Binary search on a rotated array
Use it when: a sorted array has been rotated (shifted around) and you need its minimum, its rotation point, or a value, in O(log n).
Signal words
- “rotated sorted array”
- “rotated between 1 and n times”
- “unique elements”
- “O(log n)”
- “find the minimum / pivot”
This is a different shape from the classic template. We’re not looking for a
value we can test with ===; we’re narrowing down to one position (the
minimum). That changes two things: the loop runs while lo < hi (stop when one
candidate is left), and one side uses hi = mid (keep mid, it might be the answer).
- Set
lo = 0andhi = n − 1. The minimum is somewhere innums[lo..hi]. - While
lo < hi(more than one candidate): - Compute
mid = lo + (hi − lo) // 2. - If
nums[mid] > nums[hi]: the cliff is right ofmid, andmidcan’t be the minimum (something smaller sits after it). Setlo = mid + 1. - Otherwise: the minimum is
midor something before it. Sethi = mid. - When
lo == hi, returnnums[lo].
Press Play. The bars show the cliff as a dashed line. Each round, mid is
compared with hi (amber), and the half without the cliff fades out. Try the
not rotated edge case: nums[mid] is always smaller than nums[hi], so hi
walks left until it reaches index 0.
Binary search for the cliff
nums = [3, 4, 5, 1, 2]
- lo
- 0
- mid
- —
- hi
- 4
- nums[mid]
- —
- nums[hi]
- 2
- decision
- —
- result
- —
- Minimum is in here (lo..hi)
- mid
- nums[hi], what we compare with
- Ruled out
- Minimum
The minimum is somewhere in nums[lo..hi], which starts as the whole array. We will shrink the range until only one index is left.
Which line is running?
function findMin(nums) { let lo = 0;Running now: let hi = nums.length - 1; // the minimum is always inside nums[lo..hi] while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] > nums[hi]) { lo = mid + 1; // the cliff is to the right of mid } else { hi = mid; // mid..hi is sorted, so mid might be the minimum: keep it } } return nums[lo]; // lo === hi: one candidate left}Binary search for the cliff
function findMin(nums) { let lo = 0; let hi = nums.length - 1; // the minimum is always inside nums[lo..hi] while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] > nums[hi]) { lo = mid + 1; // the cliff is to the right of mid } else { hi = mid; // mid..hi is sorted, so mid might be the minimum: keep it } } return nums[lo]; // lo === hi: one candidate left}def find_min(nums): lo, hi = 0, len(nums) - 1 # the minimum is always inside nums[lo..hi] while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] > nums[hi]: lo = mid + 1 # the cliff is to the right of mid else: hi = mid # mid..hi is sorted, so mid might be the minimum: keep it return nums[lo] # lo == hi: one candidate leftJavaScript sets lo and hi on two lines and has closing braces, so its line
numbers run ahead of Python’s; we give both.
- Line 1: define the function. (LeetCode:
var findMin = function(nums), or a method ofclass Solutionin Python.) - Lines 2–3 (JS) / line 2 (Py): the minimum is somewhere in the whole array.
- Line 4 (JS) / line 3 (Py):
lo < hi, not<=. We stop when exactly one candidate is left, because that candidate must be the answer. With<=andhi = mid, the loop would never end oncelo == hi. - Line 5 (JS) / line 4 (Py): the middle, rounded down. Because
lo < hi,midis always strictly less thanhi, so we never compare a number with itself. - Lines 6–7 (JS) / 5–6 (Py): bigger than the right end means the cliff comes after
mid.miditself can’t be the minimum (the smallernums[hi]exists), so skip it:lo = mid + 1. - Lines 8–9 (JS) / 7–8 (Py): otherwise
mid..hirises. The minimum ismidor to its left. Keepmid:hi = mid. - Line 12 (JS) / 9 (Py):
lo == hi. One candidate left: the minimum.
Comparing with the left end is ambiguous. In [1, 2, 3, 4, 5] (not rotated) and in
[3, 4, 5, 1, 2] (rotated), nums[mid] > nums[lo] is true in both, but the minimum
is on the left in the first and on the right in the second. Comparing with
nums[hi] gives the right direction in every case.
Trace nums = [4, 5, 6, 7, 0, 1, 2]. The minimum (0) is at index 4.
| lo | hi | mid | nums[mid] | nums[hi] | compare | next |
|---|---|---|---|---|---|---|
| 0 | 6 | 3 | 7 | 2 | 7 > 2: cliff is right of mid | lo = 4 |
| 4 | 6 | 5 | 1 | 2 | 1 < 2: min at mid or left | hi = 5 |
| 4 | 5 | 4 | 0 | 1 | 0 < 1: min at mid or left | hi = 4 |
| 4 | 4 | lo == hi: stop | return nums[4] = 0 |
The row where mid = 4 shows why we keep mid: nums[4] = 0 is the minimum, and hi = mid keeps
it in the range. With hi = mid − 1 we’d have thrown away the answer.
Scan every number
Time
O(n)
One look per number.
Space
O(1)
One variable for the smallest so far.
Binary search for the cliff
Time
O(log n)
Each round at least halves lo..hi. 5,000 numbers take about 13 rounds.
Space
O(1)
Just lo, hi and mid.
What to say out loud, in this order:
- “The array is two sorted runs with a cliff; the minimum is right after the cliff.”
- “Compare
nums[mid]withnums[hi]: bigger means the cliff is to the right, smaller meansmid..hiis sorted.” - “I’m narrowing to one position, so
while lo < hi,lo = mid + 1on one side andhi = midon the other.” - Cost: O(log n) time, O(1) space.
- Dry-run the not-rotated case and a two-item case.
Likely follow-up questions:
- “Return how many times it was rotated?” That’s the index of the minimum: return
lo. - “What if there are duplicates?” (Problem 154.) When
nums[mid] == nums[hi]you can’t tell which side the cliff is on, so shrink by one:hi -= 1. The worst case becomes O(n). - “Find a target value in the rotated array?” That’s Search in Rotated Sorted Array, in week 4.
Related problems:
- Binary Search (this week): the classic template this one bends.
- Search in Rotated Sorted Array (week 4): same rotated shape, looking for a target.
- The week 3 overview and its off-by-one survival guide compare both loop styles.