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.
from bisect import bisect_left print(bisect_left([10, 20, 30], 25)) # 2
Try it
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.
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
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_leftreturns the index of the first equal item andbisect_rightthe index just past the last one. For a value that is absent they agree. insortis O(n) because inserting into a list shifts items, even though the search is O(log n). For heavy insert workloads considerheapqor 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,xmust already be a key value. Ininsort(records, ("Di", 33), key=...)the item inserted is the whole record, becauseinsortapplies the key toxas 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 asarray.arrayorrange.
Related
heapq,list.sort(),list.insert()- Lessons: Algorithms, Lists