LeetCode 33 · Binary Search

Search in Rotated Sorted Array, explained with a picture

Finding a number on a turned clock face.

MediumBinary Search
▶ Watch it step by step

The problem

A sorted list was rotated at an unknown point. Given a target, return its position or −1, in O(log n) time.

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Picture it

Same turned clock face. When we cut at the middle, at least one half is still perfectly sorted (no drop inside it). We check that sorted half: if the target lies within its smallest and largest number, search there; otherwise search the other half.

How to recognise it

  • The list is sorted, then rotated at an unknown point, and you must find a position in O(log n).
  • Cut a rotated list anywhere and at least one half is fully in order. For an ordered half you can tell, from its two ends, whether the target could be inside it.
  • So each step can still throw away half the range, even though the whole list is not sorted.
  • The values are distinct, which is what makes the "which half is in order" test reliable.

Start with brute force

Scan every position.

def search_brute(a, t):
    for i, x in enumerate(a):
        if x == t:
            return i
    return -1

Time is O(n) and space is O(1). LeetCode allows at most 5,000 numbers, so the scan is not slow in practice, but the problem demands O(log n), which is about 13 comparisons for 5,000 numbers. Another option is to find the minimum first (as in LeetCode 153) and binary search the correct run: that is O(log n) too, but takes two searches.

From brute force to the idea

  1. Find the waste. The scan ignores the fact that each of the two runs is sorted.
  2. Find the ordered half. Look at a[lo], a[mid] and a[hi]. If a[lo] <= a[mid], the left half lo..mid contains no drop, so it is in order. Otherwise the drop is in the left half, which means mid..hi is in order.
  3. Use <=, not <. When only one or two items are left, lo can equal mid. A one-item half is in order, and <= says so.
  4. Ask whether the target is inside the ordered half. For an ordered left half, the target is there exactly when a[lo] <= t < a[mid] (the case t == a[mid] was already checked). If so, hi = mid - 1; if not, it can only be on the right, so lo = mid + 1.
  5. Mirror it for the right half. If a[mid] < t <= a[hi], move right with lo = mid + 1; otherwise move left with hi = mid - 1.
  6. Stop when the range is empty. As in plain binary search, the loop runs while lo <= hi and returns −1 when nothing is left.

This is the key idea: one half is always sorted, and a sorted half can tell you in O(1) whether the target is inside it.

The key idea

At every step one half is sorted. Test whether the target is inside that sorted range to choose a side.

Python solution

def search(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t:
            return mid
        if a[lo] <= a[mid]:              # left half is in order
            if a[lo] <= t < a[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                            # right half is in order
            if a[mid] < t <= a[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

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): checks every positionO(1)
One-pass binary search (shown code)O(log n): each step discards about half of lo..hiO(1): three indices

Edge cases

  • The example (target 0): returns 4; target 3 returns −1.
  • One number ([1]): returns 0 for target 1 and −1 for target 0.
  • Two numbers, rotated ([3, 1], target 1): mid == lo, the <= marks the one-item left half as ordered, the target is not in it, so the search moves right and returns 1.
  • Not rotated ([1, 2, 3, 4], target 4): the left half is always ordered and the search behaves like plain binary search; returns 3.
  • Empty list: hi starts at −1, returns −1.
  • Duplicates: the shown code assumes distinct values. For [1, 0, 1, 1, 1] and target 0 it returns −1, because a[lo] <= a[mid] is true even though the left half contains the drop. See the exercise below.

Common mistakes

  • Writing a[lo] < a[mid]. When lo == mid this calls a one-item half unordered, and [3, 1] with target 1 returns −1.
  • Testing only one end, as in t < a[mid], to decide to go left. In a rotated list a smaller target can be on the right: searching the example for 0 returns −1.
  • Applying this code to a list with repeats. It gives wrong answers without crashing.
Your turn: duplicates allowed

Now values may repeat (LeetCode 81), and you only need to return whether the target is present. For [2, 5, 6, 0, 0, 1, 2], target 0 gives True and target 3 gives False. Describe your approach, then write it if you like.

Compare with our answer

The only new problem is when a[lo] == a[mid] == a[hi]: you cannot tell which half is ordered. Neither end is the target (since a[mid] is not), so shrink both ends by one and look again. Otherwise use the same logic as before.

def search_dups(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t:
            return True
        if a[lo] == a[mid] == a[hi]:      # cannot tell which half is sorted
            lo, hi = lo + 1, hi - 1
        elif a[lo] <= a[mid]:
            if a[lo] <= t < a[mid]: hi = mid - 1
            else: lo = mid + 1
        else:
            if a[mid] < t <= a[hi]: lo = mid + 1
            else: hi = mid - 1
    return False

search_dups([1, 0, 1, 1, 1], 0) is True. The worst case is O(n), for example a list of 1s with a single 0.

A strong answer mentions: exactly which case is ambiguous, why dropping both ends is safe, and that the worst case becomes O(n).

Check what stuck

1. A circular buffer holds sorted message IDs, but the oldest entry is somewhere in the middle. You must find the slot of a given ID quickly. Which approach fits best?

2. Why can the shown code decide which half to keep with a single range check?

3. A learner writes if a[lo] < a[mid]: instead of <=. Which call now gives a wrong answer?

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