The bisect module, and search inside a design

Python ships the boundary loop. Knowing which of its two functions you want is the whole skill.

Key idea

What the two functions return

bisect_left(values, x) returns the leftmost position where x could be inserted and keep the list sorted, which is the first index whose value is at or above x.

bisect_right(values, x) returns the rightmost such position, which is the first index whose value is strictly above x.

With no duplicates they differ by nothing you would notice. With duplicates they bracket the run of equal values, and that difference is the entire reason both exist.

1from bisect import bisect_left, bisect_right2 3values = [1, 3, 3, 3, 8]4 5print(bisect_left(values, 3), bisect_right(values, 3))6print(bisect_right(values, 3) - bisect_left(values, 3))   # how many 3s7print(bisect_left(values, 4), bisect_left(values, 0), bisect_left(values, 99))

Why it works

Finding the most recent entry at or before a time

A common design need: entries are recorded with increasing timestamps, and a query asks for the value in force at some moment, meaning the latest entry whose timestamp does not exceed the query.

That is a boundary question. The first timestamp strictly above the query is bisect_right, so the entry you want sits one position before it. If that position is negative, nothing was recorded early enough and the answer is empty.

1from bisect import bisect_right2 3times = [1, 4, 4, 9]4labels = ["a", "b", "c", "d"]5 6def in_force_at(moment):7    position = bisect_right(times, moment) - 18    return labels[position] if position >= 0 else ""9 10print(in_force_at(4), in_force_at(5), in_force_at(0), in_force_at(100))

Design problems are still just problems

The problem below is presented as a class with methods rather than a single function, which makes it look like a different kind of exercise. It is not. Decide what each method must store and what each query must read, and the searching is one bisect call.

Predict the output· 5 min

Predict the output: left versus right

Type the four numbers this prints, separated by single spaces.

Python

1from bisect import bisect_left, bisect_right2 3values = [2, 4, 4, 4, 7, 9]4 5print(bisect_left(values, 4), bisect_right(values, 4),6      bisect_left(values, 5), bisect_right(values, 1))

Printed output

Problem· 25 min

Time Based Key Value Store

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Binary Search

44 / 170

Binary SearchLesson 6 of 8About 41 min