LeetCode 153 · Binary Search

Find Minimum in Rotated Sorted Array, explained with a picture

A clock face someone turned.

MediumBinary Search
▶ Watch it step by step

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

  1. 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.
  2. Compare with the right end. Look at a[mid] and a[hi]. If a[mid] > a[hi], the range mid..hi is not in order, so the drop (and the minimum) is strictly to the right of mid: lo = mid + 1.
  3. Otherwise keep mid. If a[mid] <= a[hi], then mid..hi is in order, so the smallest item in it is a[mid] itself. The minimum is at mid or to its left: hi = mid.
  4. Why the right end and not the left? Comparing with a[hi] always works, including when the list is not rotated at all. Comparing with a[lo] cannot tell "sorted, minimum at lo" apart from "the drop is to the right".
  5. Stop at one candidate. The loop runs while lo < hi and hi never skips the minimum, so when lo == 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

ApproachTimeSpace
Brute forceO(n): looks at every numberO(1)
Binary search (shown code)O(log n): the range lo..hi shrinks by about half each stepO(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): every a[mid] <= a[hi], hi walks down to 0, returns 11.
  • Two numbers ([2, 1]): mid is 0, 2 > 1, so lo becomes 1; returns 1.
  • Empty list: a[lo] raises IndexError. LeetCode promises at least one number.
  • Duplicates: the shown code relies on unique values. For [3, 3, 1, 3] it returns 3, because a[mid] == a[hi] no longer tells you which run mid is in. That is LeetCode 154, solved in the exercise below.

Common mistakes

  • Writing hi = mid - 1 in the second branch. mid may be the minimum, so [3, 1, 2] returns 3.
  • Comparing a[mid] with a[lo] and moving right whenever a[mid] >= a[lo]. For an unrotated list that moves away from the minimum.
  • Using while lo <= hi together with hi = mid. When lo == hi, hi does not move and the loop never ends.
  • Returning lo (the position) when the value is asked for, or the other way round.
Your turn: duplicates allowed

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).

Check what stuck

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?

2. In the shown code, why is hi = mid safe when a[mid] <= a[hi]?

3. A learner writes hi = mid - 1 in the else branch. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.