Binary Search
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.
Tip
Choosing between them
Want the first occurrence of a value, or how many are strictly below it? That is bisect_left. Want the position after the last occurrence, or how many are at or below it? That is bisect_right.
A useful check: the answer to how many values are less than or equal to x is always bisect_right, and how many are strictly less is always bisect_left. Deriving what you want from those two sentences beats remembering which function does what.
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.
Tip
Read that output carefully
The query at 4 returns c, the last entry stamped 4, which is what bisect_right gives you and is usually what a most-recent-wins design wants. The query at 5 also returns c, because nothing was recorded between 4 and 9 so the entry in force is still the one from time 4. The query at 0 returns the empty string, which is the gap you can see between c and d in the output.
If your design wanted the first entry at a tied timestamp instead, that is bisect_left and a different position calculation. Decide which tie-breaking rule the problem states rather than assuming.
Gotcha
The list has to stay sorted
Everything here assumes the list is sorted, and for a timestamped log that is true only if entries arrive in increasing time order. Many problems guarantee exactly that, which is why appending is enough and no insertion is needed.
If entries can arrive out of order, appending breaks the invariant silently and every later query returns nonsense. Check the guarantee, and if it is absent, use insort or keep the structure sorted some other way.
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: left versus right
Type the four numbers this prints, separated by single spaces.
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.