Using bisect and sorted lists in practice

Searching sorted data Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from bisect import bisect_left, bisect_right, insort
scores = [10, 20, 20, 30]
insort(scores, 25)
print(scores, bisect_right(scores, 25) - bisect_left(scores, 20))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [10, 20, 20, 25, 30] 3

Right: 25 is inserted in order, and three scores lie in [20, 25].

Bisect brackets a value range in two O(log n) searches, while the insert itself still shifts the items after 25.

Why not the others?
  • B [10, 20, 20, 30, 25] 3. insort keeps the list sorted.
  • C [10, 20, 20, 25, 30] 2. Both copies of 20 count, plus 25.

30-second answer

bisect_left and bisect_right find positions in a sorted list in O(log n). insort finds the spot in O(log n) but inserting into a list shifts items, so each insert is O(n). For many inserts and lookups together, use a balanced tree or a sorted-container library; for a fixed sorted list, bisect is ideal.

Practise saying it · 30 s. No recording, just a timer

Explain bisect and its costs.

Say your answer out loud, then check which of these points you covered:

  • O(log n) search
  • insort is O(n) per insert
  • Range counts with two bisects

Deep dive

bisect_left(a, x, key=...) (Python 3.10+) searches by a field of each record.

Counting values in [lo, hi] is bisect_right(a, hi) - bisect_left(a, lo).

Consistent hashing rings look up the next server clockwise with exactly this kind of search.

Common mistakes

  • Calling insort in a loop and assuming O(n log n) total.
  • Forgetting that the list must stay sorted for bisect to work.

Senior take & follow-ups

Quote the insort cost correctly; it is a common trap.

Follow-up questions

Think of your answer first, then open the hint.

  1. What replaces a balanced tree in Python?

    Show hint

    The third-party sortedcontainers.SortedList offers O(log n) adds and lookups in practice.

  2. How do you find the closest value?

    Show hint

    Check the items at the bisect position and just before it.

Similar on Backend: Consistent hashing A consistent-hashing ring is a sorted list of server hashes; finding a key's server is a binary search for the next hash clockwise.

What each operation costs: Binary Search · Linear Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.