bisect — array bisection algorithm

bisect_left and bisect_right insertion points, the key argument applying to list elements, and O(n) insort, checked on Python 3.13.12.

モジュールページの本文は現在英語です。

The bisect module locates insertion points in a list that is already sorted, using only the < operator. It does not call __eq__ to test whether a value is present. Examples were checked on Python 3.13.12.

Finding an index is O(log n). Inserting with insort still takes O(n) time because list.insert shifts elements. This page is not a heap reference; heapq remains on its own page. Official documentation also notes that these functions are not thread-safe on a shared mutable sequence.

Examples were checked against Python 3.13. See the official documentation for the complete API.

Python reference overview →

Left and right insertion points

bisect_left(a, x) is the index of the first position where x can be inserted and remain sorted: existing equal elements stay to the right. bisect_right(a, x), also available as bisect.bisect, is the position after any existing equal elements. For a = [1, 2, 2, 2, 3], both bisect_left(a, 2) and bisect_right(a, 2) are 1 and 4.

lo and hi limit the search to a slice; the official default is lo=0 and hi=len(a). The functions still assume that slice is already sorted.

bisect.bisect_left, bisect.bisect_right, bisect.bisect

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.bisect(a, x, lo=0, hi=len(a), *, key=None)

Return the leftmost or rightmost insertion index for x in a sorted list.

ParameterDescription
a / xa is a sorted sequence. x is the value to locate. When key is None, elements are compared with x directly.
lo / hiOptional bounds for the search. The official defaults consider the whole sequence.

Returns: An int index in the range lo..hi inclusive, suitable as the first argument of list.insert.

  • bisect.bisect is an alias of bisect_right.
  • These functions do not raise if x is missing; they only return an insertion point. bisect_left on an empty list returns 0.
python
import bisect

a = [1, 2, 2, 2, 3]
print(bisect.bisect_left(a, 2), bisect.bisect_right(a, 2), bisect.bisect(a, 2))
print(bisect.bisect_left(a, 0), bisect.bisect_right(a, 9))
print(bisect.bisect_left([], 1))

Expected output

1 4 4
0 5
0

Related: heapq

Official documentation →

key functions and insort

The key parameter, added in Python 3.10, is a one-argument function applied to each element of a. Official documentation states that, for bisect_left and bisect_right, the key function is not applied to x, so that you can search for a raw key in a list of records. Passing a record as x then compares that record with extracted keys and can raise TypeError, as in the example.

insort_left and insort_right (aliased as insort) call bisect_* and then list.insert. Official documentation warns that the O(log n) search is dominated by the O(n) insertion. For insort, the key is applied to x during the search, but the inserted object is x itself, not key(x).

bisect.bisect_left, bisect.insort_left, bisect.insort_right

bisect.bisect_left(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)
bisect.insort(a, x, lo=0, hi=len(a), *, key=None)

Search records with a key applied only to list elements, then insert in sorted order in linear time.

ParameterDescription
keyOptional one-argument callable. For bisect_left and bisect_right it is applied to elements of a, not to x. For insort it is applied to x during the search only; the inserted value is still x.
xFor a key search with bisect_*, pass the already extracted key, such as 1, not a whole record.

Returns: bisect_* returns an index. insort_* mutates a in place and returns None.

Raises

  • TypeError — Raised when x cannot be compared with key(element), for example when x is a tuple and key returns an int.
  • Keep a sorted already. insort does not re-sort an unsorted list.
python
import bisect

rows = [("b", 1), ("c", 1), ("a", 2)]
print(bisect.bisect_left(rows, 1, key=lambda r: r[1]), bisect.bisect_right(rows, 1, key=lambda r: r[1]))
try:
    bisect.bisect_left(rows, ("z", 1), key=lambda r: r[1])
except TypeError as err:
    print(type(err).__name__)

left = [("b", 1), ("c", 1), ("a", 2)]
bisect.insort_left(left, ("z", 1), key=lambda r: r[1])
print(left)
right = [("b", 1), ("c", 1), ("a", 2)]
bisect.insort_right(right, ("z", 1), key=lambda r: r[1])
print(right)
xs = [1, 3]
bisect.insort_left(xs, 2)
print(xs)

Expected output

0 2
TypeError
[('z', 1), ('b', 1), ('c', 1), ('a', 2)]
[('b', 1), ('c', 1), ('z', 1), ('a', 2)]
[1, 2, 3]

Official documentation →