LeetCode 35 · Binary search

Search Insert Position, explained with a picture

Where does the new book go?.

Binary search
▶ Watch it step by step

The problem

In a sorted list, return the position of the target, or the position where it should be inserted to keep the list sorted.

Input:  [1, 3, 5, 6, 9, 12, 15], target = 7
Output: 4

Picture it

Picture slotting a new book into a sorted shelf. Binary search narrows down the gap: the first book bigger than (or equal to) the new one marks the spot.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Lower-bound binary search. O(log n).

Python solution

def search_insert(a, t):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < t:
            lo = mid + 1
        else:
            hi = mid
    return 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.