Binary search in Python with bisect - Python Morsels

Binary search in Python with bisect

Python's bisect module implements binary search for you. Here's how bisect_left, bisect_right, and insort work, plus recipes for finding the closest match or all values in a range.

Trey Hunner

July 29, 2026

14 min read

Python 3.10—3.14

When looking for an element within a sorted list, binary search can be much faster than regular iteration.

If you've taken Computer Science classes, you may have learned how to implement a binary search algorithm yourself.<br>You don't need to know that in Python because the bisect module already has binary search implemented for us.

Binary search explained

I'm thinking of a number between 1 and 100.<br>You have 7 guesses.<br>After each wrong guess I'll tell you whether the number I'm thinking of is higher or lower.

What should you guess?

Here's the approach I'd use:

Guess 50 first, splitting the possible guess pool in half (bisecting it)

If the correct number is below 50, guess 25 (bisecting the remaining pool)

If the correct number is above 50, guess 75 (bisecting the remaining pool)

Repeat, splitting the possible remaining numbers in half each time

That's binary search in a nutshell.

The binary in binary search means two: every guess splits the remaining search space into two groups and rules out one of them.<br>It has nothing to do with binary numbers or ones and zeroes.<br>That same two is in the word bisect, which means to cut something into two pieces.

Try it below: each guess rules out every number on one side of it, and guessing the middle number every time will always find my number within 7 guesses.

I'm thinking of a number from 1 to 100

Guess the middle ()<br>New number

If you'd prefer to see code, here's an example:

def binary_search(sequence, target, low=0, high=None):<br>"""Return the index where the target number would belong."""<br>if high is None:<br>high = len(sequence)<br>while low high:<br>middle = (low + high) // 2<br>if sequence[middle] target:<br>low = middle + 1<br>else:<br>high = middle<br>return low

That binary_search function looks for a potential match within a sorted sequence.

Why should we care about this, though?<br>Why not just use a containment check with the in operator?

Well, this binary search among 10 million items does 23 comparisons :

sequence = list(range(10_000_000))<br>target = 2_728_839

index = binary_search(sequence, target)<br>if index len(sequence) and sequence[index] == target:<br>print(f"{target} found")

But this containment check of the same items does well over 2 million comparisons :

sequence = list(range(10_000_000))<br>target = 2_728_839

if target in sequence:<br>print(f"{target} found")

You can see for yourself how much quicker binary search is.<br>That's the difference between O(log n) and O(n): doubling the size of our sorted list adds just one more comparison to a binary search.

Note that both of those examples above are a bit silly because those "sorted sequences" are consecutive numbers without gaps or duplicates.<br>We'll take a look at a more realistic example below.<br>But first, let's talk about why we can't always use a set or a dictionary instead of binary search.

Why not use a set instead of binary search?

If you're familiar with the performance of Python's data structures, you might be thinking, "instead of binary search on a sorted sequence, why wouldn't we use a dictionary or a set for quick lookups ?"

Looking up a key in a dictionary is a constant time operation, meaning it doesn't get slower as a dictionary grows in size.<br>Checking whether a set contains a specific value is also a constant time operation.<br>For more on the phrase "constant time" and on time complexity in Python more generally, see my article on time complexity and Big-O in Python.

If we put our 10 million sorted items in a set, we could perform a containment check to find a match very quickly:

if target in my_set:<br>print(f"{target} found")

But what if we're not looking for an exact match?

Imagine that we need all the matches between two numbers.<br>Or imagine that we want to know what the closest match would be when there isn't an exact match.

We can't perform those operations quickly with a set or a dictionary.

Sets and dictionaries are often great for quick containment checks, but they don't work when our containment checks are inexact .<br>Fuzzy containment checks are what binary search excels at.

In Python, you don't need to implement binary search yourself: the bisect module already does that.

Binary search with the bisect module

Python's bisect module implements various utilities for locating items in sorted collections and inserting items into them, all using binary search.

The bisect module includes these 4 functions:

bisect_left & bisect_right : return the index where we could insert an item into a sorted sequence

insort_left & insort_right : insert an item into a sorted sequence

The bisect_* functions perform a binary search , and the insort_* functions insert an item in the...