`Lib/bisect.py`

cpython 3.14 @ ab2d84fe1023/Lib/bisect.py

bisect.py provides binary search over sorted sequences. The two core search functions, bisect_left and bisect_right, return the insertion point that keeps the sequence sorted after an insert. The two insert functions, insort_left and insort_right, call the corresponding search function and then perform the actual list.insert. The module exposes bisect as an alias for bisect_right and insort as an alias for insort_right, matching the most common use case of finding the rightmost position where an item could be inserted.

The pure-Python implementations use classic binary search with a lo/hi pair narrowing toward the target. Each iteration computes mid = (lo + hi) // 2, compares a[mid] to x, and advances either lo or hi. The loop exits when lo == hi, at which point lo is the insertion index. The key parameter, added in Python 3.10, maps each array element through a callable before comparison, mirroring the key convention of sorted and list.sort. When key is supplied the implementation precomputes key(x) once and applies key to each array element during the search.

At the bottom of the file the module attempts from _bisect import *, replacing the pure-Python definitions with compiled equivalents from the _bisect C extension module. The C versions are faster for large lists because they avoid per-iteration Python attribute lookups and can use the CPython sequence protocol directly. If _bisect is not available (e.g. during early bootstrap or on exotic platforms) the pure-Python fallbacks remain active silently.

Map

Lines	Symbol	Role	gopy
1-5	module header	Docstring and `__all__` declaration	-
6-40	`bisect_right`	Find rightmost insertion point, optional `key`	-
41-75	`bisect_left`	Find leftmost insertion point, optional `key`	-
76-95	`insort_right`	Insert keeping sort order (right bias)	-
96-115	`insort_left`	Insert keeping sort order (left bias)	-
116-125	C accelerator import	`from _bisect import *` with silent fallback	-

Reading

bisect_right (lines 6 to 40)

cpython 3.14 @ ab2d84fe1023/Lib/bisect.py#L6-40

bisect_right returns the index after any existing entries equal to x. This is the standard "upper bound" operation. The lo and hi parameters let callers restrict the search to a sub-range without slicing the list. When key is not None, each comparison uses key(a[mid]) rather than a[mid] directly. Because the key function is applied to list elements and not to x, the caller is expected to pass the pre-mapped value of x as needed, matching how sorted(a, key=...) works.

def bisect_right(a, x, lo=0, hi=None, *, key=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < a[mid]:
                hi = mid
            else:
                lo = mid + 1
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < key(a[mid]):
                hi = mid
            else:
                lo = mid + 1
    return lo

bisect_left (lines 41 to 75)

cpython 3.14 @ ab2d84fe1023/Lib/bisect.py#L41-75

bisect_left returns the leftmost position where x could be inserted, meaning any existing equal elements remain to the right of the insertion point. The only structural difference from bisect_right is the comparison direction: the inner branch tests a[mid] < x (strict less-than) and advances lo when true, while bisect_right tests x < a[mid] and advances hi. This single asymmetry produces the left/right split between the two functions.

def bisect_left(a, x, lo=0, hi=None, *, key=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

insort helpers (lines 76 to 115)

cpython 3.14 @ ab2d84fe1023/Lib/bisect.py#L76-115

insort_right and insort_left are thin wrappers: they call the corresponding bisect_* function to find the index, then call a.insert(index, x). The key parameter is forwarded to the bisect call, but note that list.insert always stores the original x, not key(x). This means the key function is purely for the purpose of locating the insertion point; the stored value is unmodified. Both insort functions have an O(n) cost because list.insert shifts elements.

def insort_right(a, x, lo=0, hi=None, *, key=None):
    lo = bisect_right(a, x, lo, hi, key=key)
    a.insert(lo, x)

def insort_left(a, x, lo=0, hi=None, *, key=None):
    lo = bisect_left(a, x, lo, hi, key=key)
    a.insert(lo, x)

C accelerator override (lines 116 to 125)

cpython 3.14 @ ab2d84fe1023/Lib/bisect.py#L116-125

The final lines unconditionally import everything from _bisect, overwriting the pure-Python names if the C extension is available. The try/except ImportError block makes the pure-Python definitions the fallback. This pattern keeps the file self-contained and testable without the C extension while giving fast paths in normal CPython builds.

try:
    from _bisect import *
except ImportError:
    pass

gopy mirror

Not yet ported. The pure-Python implementation is straightforward to translate to Go. A natural Go equivalent would be a generic function using cmp.Ordered or an explicit comparator, with sort.SearchInts / sort.Search from the Go standard library as a reference point. When ported it should live at module/bisect/.

Map​

Reading​

bisect_right (lines 6 to 40)​

bisect_left (lines 41 to 75)​

insort helpers (lines 76 to 115)​

C accelerator override (lines 116 to 125)​

gopy mirror​

Map