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 Trey Hunner 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. 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. You have 7 guesses. 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. It has nothing to do with binary numbers or ones and zeroes. 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

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

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

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

Why should we care about this, though? 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))
target = 2_728_839

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

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

sequence = list(range(10_000_000))
target = 2_728_839

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

You can see for yourself how much quicker binary search is. 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. We'll take a look at a more realistic example below. But first, let's talk about why we can't always use a set or a dictionary 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. Checking whether a set contains a specific value is also a constant time operation. 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:
    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. 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. 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 correct location to maintain a sequence's sorted order.

The bisect module also includes these 2 aliases:

  • bisect: does the same thing as bisect_right
  • insort: does the same thing as insort_right

You might be wondering: why are there two different bisect_* functions? And why do bisect_left and bisect_right return an index instead of just True or False?

Essentially, these are general-purpose tools that can be used in a few different ways. Let's take a look at how they work.

Python's bisect functions explained

The bisect_left and bisect_right functions return an index where a target value could be inserted to maintain sorted order.

When given a value that isn't (yet) present within a sorted collection, bisect_left and bisect_right both return the same number:

>>> from bisect import bisect_left, bisect_right
>>> numbers = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
>>> bisect_left(numbers, 60)
10
>>> bisect_right(numbers, 60)
10

That number 10 is the index where the number 60 should be if it were inserted into our numbers list. Index 10 is where 89 is right now, and it's just after where 55 is:

>>> numbers[10]
89
>>> numbers[10-1]
55

So when the item isn't present in the sorted sequence, bisect_left and bisect_right return the same index.

When the item is present, bisect_left and bisect_right return 2 different indexes.

When the item is present, bisect_left returns the index of the left-most match:

>>> bisect_left(numbers, 1)
0
>>> numbers[0]  # 1 is found at index 0
1

When the item is present, bisect_right returns the index just after the right-most match:

>>> bisect_right(numbers, 1)
2
>>> numbers[2]  # 1 is NOT found at index 2
2

If we sliced from the bisect_left index to the bisect_right index, we would get a slice of all the matching values:

>>> value = 1
>>> numbers[bisect_left(numbers, value):bisect_right(numbers, value)]
[1, 1]

Note that these are general-purpose functions, so they're a bit lower-level than you might want for your binary search needs. It's common to wrap these functions in higher-level recipes.

Binary search recipes using Python's bisect

The Python documentation includes a few recipes for functions that you might use to make bisect_left and bisect_right more useful. Below are variations of those functions as well as a few more that the documentation doesn't include.

Check whether a sorted sequence contains a value

Here's a function that returns True if there's an exact match and False if there's not:

def has_match(sequence, target, key=None):
    """Return True if sorted sequence has value exactly equal to target."""
    index = bisect_left(sequence, target, key=key)
    if index == len(sequence):
        return False
    found = sequence[index]
    if key is not None:
        found = key(found)
    return found == target

Count the matching values in a sorted sequence

This function returns the number of matches (like the list count method but much faster for large sorted sequences):

def count(sequence, target, key=None):
    """Return number of values exactly equal to target."""
    low = bisect_left(sequence, target, key=key)
    high = bisect_right(sequence, target, key=key)
    return high - low

Find the index of the first or last match

Here are 2 functions that return the index of the first and last matching values (they raise a ValueError if there's no match):

def index(sequence, target, key=None):
    """Locate index of the left-most value exactly equal to target."""
    index_ = bisect_left(sequence, target, key=key)
    if index_ < len(sequence):
        found = sequence[index_]
        if key is not None:
            found = key(found)
        if found == target:
            return index_
    raise ValueError("Target value not found")


def rindex(sequence, target, key=None):
    """Locate index of the right-most value exactly equal to target."""
    index_ = bisect_right(sequence, target, key=key) - 1
    if index_ >= 0:
        found = sequence[index_]
        if key is not None:
            found = key(found)
        if found == target:
            return index_
    raise ValueError("Target value not found")

Find the nearest value above or below a target

These 4 functions return specific values that are on either side of the target value:

def find_lt(sequence, target, key=None):
    """Find right-most value less than target."""
    index = bisect_left(sequence, target, key=key)
    if index > 0:
        return sequence[index-1]
    raise ValueError("All values are >= target")


def find_le(sequence, target, key=None):
    """Find right-most value less than or equal to target."""
    index = bisect_right(sequence, target, key=key)
    if index > 0:
        return sequence[index-1]
    raise ValueError("All values are > target")


def find_gt(sequence, target, key=None):
    """Find left-most value greater than target."""
    index = bisect_right(sequence, target, key=key)
    if index < len(sequence):
        return sequence[index]
    raise ValueError("All values are <= target")


def find_ge(sequence, target, key=None):
    """Find left-most value greater than or equal to target."""
    index = bisect_left(sequence, target, key=key)
    if index < len(sequence):
        return sequence[index]
    raise ValueError("All values are < target")

Find the closest value in a sorted sequence

This function returns the closest match or an exact match when there is one (values must be subtractable, like numbers or dates):

def closest(sequence, target, key=None):
    """
    Return the value nearest to target.

    In the case of a tie, the smaller value is returned.
    """
    if not sequence:
        raise ValueError("Sequence is empty")
    index = bisect_left(sequence, target, key=key)
    if index == 0:
        return sequence[0]
    if index == len(sequence):
        return sequence[-1]
    before, after = sequence[index-1], sequence[index]
    if key is not None:
        before, after = key(before), key(after)
    if after - target < target - before:
        return sequence[index]
    return sequence[index-1]

Find all values between two values

These functions return all items between two values:

def between(sequence, low, high, key=None):
    """Return all values from low (inclusive) to high (exclusive)."""
    low_index = bisect_left(sequence, low, key=key)
    high_index = bisect_left(sequence, high, key=key)
    return sequence[low_index:high_index]


def between_inclusive(sequence, low, high, key=None):
    """Return all values between low and high values (inclusive)."""
    low_index = bisect_left(sequence, low, key=key)
    high_index = bisect_right(sequence, high, key=key)
    return sequence[low_index:high_index]


def between_exclusive(sequence, low, high, key=None):
    """Return all values between low and high values (exclusive)."""
    low_index = bisect_right(sequence, low, key=key)
    high_index = bisect_left(sequence, high, key=key)
    return sequence[low_index:high_index]

Binary insert with insort

In addition to the various bisect functions, the bisect module also has insort functions for inserting an element into a sorted sequence while maintaining sorted order.

The insort functions are basically implemented like this:

def insort_left(sequence, item, lo=0, hi=None, *, key=None):
    target = item if key is None else key(item)
    sequence.insert(bisect_left(sequence, target, lo, hi, key=key), item)


def insort_right(sequence, item, lo=0, hi=None, *, key=None):
    target = item if key is None else key(item)
    sequence.insert(bisect_right(sequence, target, lo, hi, key=key), item)


insort = insort_right

The bisect.insort function is really just a shorthand for calling the list insert method with the index that's returned from bisect.bisect.

The binary search part of insort is fast, but the insertion isn't. The list insert method needs to shift over every item after the insertion index, so insort takes O(n) time overall. Binary search saves you the search, not the insert.

Using bisect with a key function

You may have noticed that both the bisect_* and insort_* functions accept a key argument. That optional key argument is a key function: a function which is called on each item that's inspected during the search. The values that function returns are what actually get compared.

For example, say we have a sorted list of words but the words have different capitalizations and some words contain punctuation:

words = [
    "C++", "caseless", "GitHub", "GZip", "heterogeneous", "inexhaustible",
    "IPython", "Jupyter", "octothorpe", "O'Reilly", "profiler",
    "programmatically", "symlinks", "templating", "uncomment",
]

This list is sorted in a way that ignores capitalization and punctuation. Which means any binary search we perform on it also needs to ignore capitalization and punctuation.

We could make a normalize function that ignores capitalization and non-letters:

def normalize(string):
    return "".join(c for c in string.casefold() if c.isalpha())

And then we can pass that function as the key argument when searching:

>>> from bisect import bisect_left
>>> index = bisect_left(words, "ipython", key=normalize)
>>> words[index]
'IPython'

In Python, you can pass functions to other functions. Python's sorted, min, and max functions, along with various other functions that compare using ordering operators (<, >, etc.), will accept a key function to use when ordering. The various bisect utilities accept that same sort of key function.

Our original example of searching 10 million consecutive numbers was a bit silly. Real-world data usually has gaps and duplicates, and we're often searching it inexactly.

Say we have thousands of temperature readings, sorted by date, but with some missing days. Here are the first few readings:

from datetime import date

temperatures = [
    (date(2000, 7, 1), 78),
    (date(2000, 7, 2), 75),
    (date(2000, 7, 5), 71),
    (date(2000, 7, 6), 74),
    (date(2000, 7, 9), 80),
    (date(2000, 7, 12), 77),
    (date(2000, 7, 15), 72),
    # Imagine thousands more readings here
]

We could use our between_inclusive function (with a key function that grabs the date from each tuple) to find all readings within a given date range:

>>> from operator import itemgetter
>>> start = date(2000, 7, 2)
>>> end = date(2000, 7, 9)
>>> between_inclusive(temperatures, start, end, key=itemgetter(0))
[(datetime.date(2000, 7, 2), 75), (datetime.date(2000, 7, 5), 71), (datetime.date(2000, 7, 6), 74), (datetime.date(2000, 7, 9), 80)]

We could use our find_le function to answer the question "what was the most recent reading on or before this date?"

>>> find_le(temperatures, date(2000, 7, 8), key=itemgetter(0))
(datetime.date(2000, 7, 6), 74)

Or we could use our closest function to find the reading that was taken closest to a given date:

>>> closest(temperatures, date(2000, 7, 8), key=itemgetter(0))
(datetime.date(2000, 7, 9), 80)

There's no July 8 reading, so we got July 9's reading instead (July 9 is closer to July 8 than July 6 is).

None of these lookups could be done easily with a set or a dictionary because none of them are exact lookups. And on a large enough sorted list, each of these lookups will be much faster than looping over the whole list.

Don't use binary search on an unsorted collection

Binary search only works on sorted data.

The bisect functions won't check that your sequence is sorted (that check would require looping over the whole sequence, which would defeat the point of binary search). If you call them on an unsorted list, you won't get an error: you'll just get a wrong answer.

>>> from bisect import bisect_left
>>> numbers = [29, 4, 12, 18, 3]
>>> bisect_left(numbers, 3)
0

The number 3 is in that list (at index 4), but bisect_left claims it belongs at index 0. Binary search assumed that since numbers[2] (which is 12) was bigger than 3, our target must be in the first half of the list. That assumption only holds for sorted data.

Also keep in mind that sorting is more expensive than searching. Sorting a list takes more time than looping over it, so if you only need to perform one lookup, sorting your data just to use bisect will actually slow you down.

For a one-off "closest match" question on unsorted data, you could just use the min function with a key function:

>>> min(numbers, key=lambda n: abs(n - 10))
12

Binary search pays off when your data is already sorted, or when you'll perform many searches on the same data after sorting it once.

Use bisect to search sorted sequences in Python

If you need to look up an exact match, and you can use a set or a dictionary, use one: that's what they excel at.

But if your data is sorted and your lookups are inexact (the closest value, the next value, all values in a range), that's where binary search shines.

You don't need to implement binary search yourself. Python's bisect module has already done it for you: bisect_left and bisect_right for searching, and insort for inserting into a sorted list.

The bisect functions are general purpose and a bit low-level, so don't be afraid to wrap them in a helper function (like the recipes above) with a name that says what your code actually means.

✕
↑
A Python Tip Every Week

Need to fill-in gaps in your Python skills? I send weekly emails designed to do just that.