The problem
A sorted list has been rotated (some numbers from the front moved to the back, e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Find the smallest number in O(log n) time.
Input: [4, 5, 6, 7, 0, 1, 2] Output: 0
Picture it
Picture the numbers written in order around a clock face, and then someone turned the clock. Somewhere there’s a “drop” where a big number is followed by a small one: that small number is the minimum. Compare the middle number with the rightmost: if middle > right, the drop is in the right half; otherwise it’s in the left half (or at the middle itself).
How to recognise it
- The list was sorted, then rotated: it is two sorted runs, and the second run's values are all smaller than the first's.
- You are asked for O(log n), so a full scan is ruled out even though it would be easy.
- One comparison tells you which side of the drop a position is on: a value bigger than the last item must be in the first (higher) run.
- That yes/no test flips exactly once along the list, so binary search can find the boundary. The minimum is the first item of the second run.
Start with brute force
Look at every number and keep the smallest.
def find_min_brute(a):
return min(a)
Time is O(n) and space is O(1). With LeetCode's limit of 5,000 numbers that is only 5,000 comparisons, so it is not slow in practice, but it ignores the structure and the problem explicitly asks for O(log n): about 13 comparisons for 5,000 numbers.
From brute force to the idea
- Find the waste. The list is almost sorted. Within each run, the smallest item is always the first one, so only the position of the drop matters.
- Compare with the right end. Look at
a[mid]anda[hi]. Ifa[mid] > a[hi], the rangemid..hiis not in order, so the drop (and the minimum) is strictly to the right ofmid:lo = mid + 1. - Otherwise keep
mid. Ifa[mid] <= a[hi], thenmid..hiis in order, so the smallest item in it isa[mid]itself. The minimum is atmidor to its left:hi = mid. - Why the right end and not the left? Comparing with
a[hi]always works, including when the list is not rotated at all. Comparing witha[lo]cannot tell "sorted, minimum atlo" apart from "the drop is to the right". - Stop at one candidate. The loop runs
while lo < hiandhinever skips the minimum, so whenlo == hi,a[lo]is the answer.
This is the key idea: comparing the middle with the last item tells you which run the middle is in, and the minimum is where the second run starts.
The key idea
Compare nums[mid] with nums[hi] to know which half holds the rotation point, and binary search into it.
Python solution
def find_min(a):
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] > a[hi]:
lo = mid + 1 # the drop is to the right of mid
else:
hi = mid # mid..hi is sorted; min is at mid or left
return a[lo]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n): looks at every number | O(1) |
| Binary search (shown code) | O(log n): the range lo..hi shrinks by about half each step | O(1): two indices |
Edge cases
- The example (
[4, 5, 6, 7, 0, 1, 2]): returns 0. - One number (
[1]): the loop never runs, returns 1. - Not rotated (
[11, 13, 15, 17], a rotation by n): everya[mid] <= a[hi],hiwalks down to 0, returns 11. - Two numbers (
[2, 1]):midis 0,2 > 1, solobecomes 1; returns 1. - Empty list:
a[lo]raisesIndexError. LeetCode promises at least one number. - Duplicates: the shown code relies on unique values. For
[3, 3, 1, 3]it returns 3, becausea[mid] == a[hi]no longer tells you which runmidis in. That is LeetCode 154, solved in the exercise below.
Common mistakes
- Writing
hi = mid - 1in the second branch.midmay be the minimum, so[3, 1, 2]returns 3. - Comparing
a[mid]witha[lo]and moving right whenevera[mid] >= a[lo]. For an unrotated list that moves away from the minimum. - Using
while lo <= hitogether withhi = mid. Whenlo == hi,hidoes not move and the loop never ends. - Returning
lo(the position) when the value is asked for, or the other way round.
Now the numbers may repeat, for example [3, 3, 1, 3] or [1, 3, 3]. Find the minimum. Describe your approach, then write it if you like.
Compare with our answer
The two clear cases stay the same. The new case is a[mid] == a[hi]: you cannot tell which run mid is in. But a[hi] has a copy at mid, so dropping a[hi] cannot lose the minimum's value. Shrink hi by one and try again.
def find_min_dups(a):
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] > a[hi]:
lo = mid + 1
elif a[mid] < a[hi]:
hi = mid
else:
hi -= 1 # a[hi] has a copy at mid, so drop it
return a[lo]
find_min_dups([3, 3, 1, 3]) is 1. It is O(log n) on most inputs, but a list like [1, 1, 1, 0, 1] can force O(n), since equal values give no information.
A strong answer mentions: why equality is ambiguous, why dropping a[hi] is safe, and that the worst case becomes O(n).
1. A sensor log is sorted by time, but it wraps around once a day, so it looks like [22:00, 23:00, 00:00, 01:00]. You must find the earliest time of day. Which approach fits best?
The log is a rotated sorted list, so comparing with the last entry finds the start of the second run in O(log n). Sorting is O(n log n), the scan is O(n), and plain binary search assumes one sorted run.
2. In the shown code, why is hi = mid safe when a[mid] <= a[hi]?
If mid..hi is sorted, nothing to the right of mid can be smaller than a[mid], so the minimum is at mid or before it. Values right of mid are not always larger in a rotated list, which is why the comparison is needed at all.
3. A learner writes hi = mid - 1 in the else branch. Which input now gives a wrong answer?
In [3, 1, 2] the first mid is the 1 itself; 1 <= 2, so hi = mid - 1 skips it and the function returns 3. In the other inputs the minimum is never at a mid that lands in the else branch, so the bug stays hidden.
Score 60% or more and the lesson is marked complete.