Skip to content
Tutorials Center
My learning

Topics

Python Reference ยท Standard Library: Data Structures and Functional Tools

The bisect module

Reference for Python's bisect module: binary search with bisect_left and bisect_right, insort, the key parameter, range lookups and grade-table examples.

bisect performs binary search on a list that is already sorted. It finds where a value belongs in logarithmic time, and insort inserts it there so the list stays sorted.

Note that the functions give an insertion position, not a yes/no answer. You turn that into a membership test by checking the element at that position.

Python
from bisect import bisect_left

print(bisect_left([10, 20, 30], 25))  # 2

Try it

Python Finding positions and inserting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python Lookup tables and the key parameter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Syntax

Python
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)
bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
Name Description
a A sorted sequence (for insort, a mutable list).
x The value to locate or insert.
lo, hi Optional slice of a to search.
key Optional function applied to each element of a for comparison (3.10+). It is not applied to x for the search functions.

bisect is an alias for bisect_right, and insort for insort_right.

Return value: bisect_* return an integer index; insort_* return None and modify the list.

Raises: TypeError for items that cannot be compared; ValueError if lo is negative.

Usage notes

  • The input must be sorted by the same ordering you search with. On unsorted data the result is silently meaningless.
  • Left vs right: for a value that is already present, bisect_left returns the index of the first equal item and bisect_right the index just past the last one. For a value that is absent they agree.
  • insort is O(n) because inserting into a list shifts items, even though the search is O(log n). For heavy insert workloads consider heapq or a different structure.
  • Range lookups such as grade bands, tax brackets and time slots are the best use: keep a sorted list of boundaries and a parallel list of labels.
  • With key, x must already be a key value. In insort(records, ("Di", 33), key=...) the item inserted is the whole record, because insort applies the key to x as well (3.10+).
  • Pre-3.10 code stored a parallel list of keys, or inserted (key, value) tuples.
  • Works on any sorted sequence with indexing and len, such as array.array or range.