Binary Search with bisect

The bisect module performs binary search on a sorted list: it finds in O(log n) time exactly where a value belongs, so you can locate items, look up grade boundaries, or insert while keeping the list sorted — without ever re-sorting.

Learn Binary Search with bisect in our free Python course — an interactive lesson with runnable examples, a practice exercise and a quick reference.

Part of the free Python course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

Searching a sorted list one element at a time is slow. bisect halves the problem on every step, making lookups in huge sorted lists feel instant.

Both functions answer "where would this value go to keep the list sorted?" — returning an index, not changing the list. They differ only when the value already exists: bisect_left lands before existing copies, bisect_right lands after them:

insort_left and insort_right find the right spot and insert there, so your list stays sorted as it grows — no need to call sort() again:

Each insort finds the position in O(log n), though the actual insertion into a list is O(n) because later elements shift. For a "keep this leaderboard sorted as scores trickle in" workload it's exactly right.

One of bisect's classic uses: map a number to a category by finding which bucket it falls into. Define the boundaries, bisect the score, and index into your labels — the technique behind the official Python docs example:

Replace each ___ so new scores are inserted in their correct sorted position.

With two bisects you can count how many values fall inside any range [low, high] in O(log n), without scanning.

Lesson complete — binary search is in your toolkit!

You can find insertion points with bisect_left and bisect_right , keep a list sorted with insort , map numbers to categories with a boundary lookup, and count values in a range — all in O(log n), and you know never to bisect an unsorted list.

🚀 Up next: Numbers — int, float, Decimal & Fraction — exact arithmetic and float pitfalls.

Practice quiz

What does bisect.bisect_left and bisect_right do to the list?

  • They insert the value
  • They return an index without changing the list
  • They sort the list
  • They remove the value

Answer: They return an index without changing the list. Both return an insertion index; they do not modify the list (insort does the inserting).

For data = [10, 20, 20, 20, 30, 40], what is bisect.bisect_left(data, 20)?

  • 1
  • 4
  • 0
  • 3

Answer: 1. bisect_left lands before existing equal values, so it returns index 1.

For the same data, what is bisect.bisect_right(data, 20)?

  • 1
  • 2
  • 4
  • 5

Answer: 4. bisect_right lands after the last equal value, returning index 4.

When the value is NOT already in the sorted list, how do bisect_left and bisect_right compare?

  • left is always smaller
  • right is always smaller
  • They return the same index
  • They both raise an error

Answer: They return the same index. They differ only on duplicates; for an absent value both return the same insertion point.

What is the time complexity of a bisect search on a sorted list?

  • O(n)
  • O(log n)
  • O(1)
  • O(n log n)

Answer: O(log n). Binary search halves the search space each step, giving O(log n).

What does bisect_right(data, x) - bisect_left(data, x) compute?

  • The index of x
  • How many times x appears in the sorted list
  • Whether x is present (0 or 1)
  • The sum of all x values

Answer: How many times x appears in the sorted list. The gap between the two indices equals the count of x in the sorted list — in O(log n).

What does bisect.insort(scores, value) do?

  • Returns an index only
  • Inserts value at its correct sorted position
  • Sorts the entire list
  • Removes value from the list

Answer: Inserts value at its correct sorted position. insort finds the position (O(log n)) and inserts the value, keeping the list sorted.

What happens if you call bisect on an UNSORTED list?

  • It raises a ValueError
  • It sorts the list first
  • It returns a wrong index with no error (silent bug)
  • It returns -1

Answer: It returns a wrong index with no error (silent bug). bisect assumes sorted input and never checks — on unsorted data it silently returns wrong results.

Although insort finds the spot in O(log n), why is the overall insertion O(n)?

  • Because it re-sorts the list
  • Because later elements must shift to make room
  • Because it copies the whole list twice
  • Because binary search is actually linear

Answer: Because later elements must shift to make room. Inserting into a list shifts later elements, which is O(n) even though finding the spot is O(log n).

In the grade lookup grades[bisect.bisect_right(breakpoints, score)] with breakpoints [60,70,80,90] and grades ["F","D","C","B","A"], what grade does a score of 90 get?

  • "B"
  • "A"
  • "C"
  • "F"

Answer: "A". bisect_right([60,70,80,90], 90) is 4, and grades[4] is "A".