Core pattern

Binary search: finding a book on a sorted shelf

Learn the binary search pattern through one picture you won’t forget, worked on Binary Search.

The example 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.

The key idea

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

Python

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

Practise binary search

NeetCode 150 problems that use it

Binary Search ·