LeetCode 704 · Binary Search

Binary Search, explained with a picture

Finding a book on a sorted shelf.

EasyBinary Search
▶ Watch it step by step

The problem

Given a list of numbers sorted from small to large and a target number, return the position of the target, or −1 if it is not in the list.

Input:  [3,7,12,18,23,29,34,38,42,47,51,56,63,70,77], target = 42
Output: 8   (positions count from 0)

Picture it

Picture a long library shelf where books are arranged by number. Instead of checking books one by one, pull out the middle book. If its number is too small, the book you want must be in the right half, so you can ignore the whole left half. Too big? Ignore the right half. Each look throws away half the shelf, so even 1,000 books need only about 10 looks.

How to recognise it

  • The input is sorted, and you are looking for a value or a position.
  • One comparison with a middle item tells you which half cannot contain the answer, so you can throw that half away.
  • The problem asks for O(log n) time, which almost always means binary search.
  • The same idea works on anything with a yes/no test that flips once from "too small" to "big enough": positions in a list, a speed, a capacity, a time.

Start with brute force

Walk through the list from the start and return the first position that holds the target.

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

Time is O(n) and space is O(1). With LeetCode's limit of 10^4 numbers that is only 10^4 comparisons, so it would pass the tests, but the problem explicitly asks for O(log n). Binary search needs about 14 comparisons for 10^4 numbers, and about 30 for 10^9. The gap matters when the list is huge or you search it many times.

From brute force to the idea

  1. Find the waste. A linear scan ignores the fact that the list is sorted. Comparing the target with any one item tells you whether the target is to the left or the right of it.
  2. Compare with the middle. Keep an inclusive range lo..hi where the target could still be. Look at mid = (lo + hi) // 2.
  3. Discard half. If books[mid] == target, return mid. If books[mid] < target, everything up to mid is too small, so lo = mid + 1. Otherwise everything from mid on is too big, so hi = mid - 1.
  4. Always move past mid. Because mid has been checked, the new range excludes it. That is what guarantees the range shrinks every step and the loop ends.
  5. Stop when the range is empty. The loop runs while lo <= hi. When lo > hi no position is left, so return −1.

This is the key idea: each comparison with the middle item rules out half of the remaining positions.

The key idea

Keep a range [lo, hi] that must contain the answer and halve it every step: O(log n).

Python solution

def search(books, target):
    lo, hi = 0, len(books) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if books[mid] == target:
            return mid
        if books[mid] < target:
            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): may compare with every itemO(1)
Binary search (shown code)O(log n): the range halves every step, so about log2(n) + 1 comparisons at mostO(1): only lo, hi and mid

Edge cases

  • Empty list: hi starts at −1, the loop never runs, returns −1. LeetCode promises at least one number.
  • One number ([5], target 5): lo == hi == 0, so the loop must use <=; returns 0.
  • Target smaller or larger than everything ([1, 3] with 0 or 4): the range empties off one end and the function returns −1.
  • The example (target 42): returns 8.
  • Duplicates ([2, 2, 2, 2, 2], target 2): returns 2, the first middle that matches, not the first copy. The problem has unique values; for the first copy use the lower-bound version below.
  • Overflow: Python integers cannot overflow. In Java or C++ write lo + (hi - lo) / 2, because lo + hi can exceed the integer limit on very large arrays.

Common mistakes

  • Writing while lo < hi with an inclusive hi. When one candidate is left it is never checked, so [5] with target 5 returns −1.
  • Setting lo = mid instead of mid + 1. With two items left, mid equals lo, the range stops shrinking, and the loop never ends.
  • Starting with hi = len(books) but keeping while lo <= hi. Searching [1] for 5 then reads books[1] and raises IndexError.
Your turn: where would it go?

Return the first position whose value is at least the target. If the target is present that is its first copy; if not, it is where it would be inserted to keep the list sorted. For [1, 3, 5] and target 4 the answer is 2; for target 9 it is 3. Describe your approach, then write it if you like.

Compare with our answer

Search for a boundary instead of a value. Use a half-open range lo..hi with hi = len(a), because the answer can be just past the end. If a[mid] < target, the answer is to the right of mid; otherwise mid itself might be the answer, so keep it with hi = mid.

def first_at_least(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

first_at_least([2, 2, 2, 2, 2], 2) is 0. This is what Python's bisect.bisect_left does. Time O(log n), space O(1).

A strong answer mentions: why hi starts at len(a), why hi = mid (not mid - 1) keeps a possible answer, and why while lo < hi ends with lo == hi as the answer.

Check what stuck

1. A log file has one line per second, sorted by timestamp. You must find the first line at or after 10:00. Which approach fits best?

2. The shown code searches 10^6 sorted numbers. About how many comparisons does it need in the worst case?

3. A learner writes while lo < hi: and keeps the rest of the shown code. Which call now returns a wrong answer?

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