Classic problem · Binary search

剑指 Offer 53-I, explained with a picture

How many copies of this book?.

Binary search
▶ Watch it step by step

The problem

Count how many times a target appears in a sorted list.

Input:  [5, 7, 7, 8, 8, 8, 10, 12], target = 8
Output: 3

Picture it

Picture the shelf again. Find, with binary search, where the target’s copies start and where the first bigger book starts. The distance between them is the count.

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

The key idea

upper_bound − lower_bound. O(log n).

Python solution

def count(a, t):
    def first_greater(x):        # first spot with a value > x
        lo, hi = 0, len(a)
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] <= x:
                lo = mid + 1
            else:
                hi = mid
        return lo
    return first_greater(t) - first_greater(t - 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.