8.6.bisect — Array bisection algorithm

Source code:Lib/bisect.py

This module provides support for maintaining a list in sorted order withouthaving to sort the list after each insertion. For long lists of items withexpensive comparison operations, this can be an improvement over the more commonapproach. The module is calledbisect because it uses a basic bisectionalgorithm to do its work. The source code may be most useful as a workingexample of the algorithm (the boundary conditions are already right!).

The following functions are provided:

bisect.bisect_left(a,x,lo=0,hi=len(a))

Locate the insertion point forx ina to maintain sorted order.The parameterslo andhi may be used to specify a subset of the listwhich should be considered; by default the entire list is used. Ifx isalready present ina, the insertion point will be before (to the left of)any existing entries. The return value is suitable for use as the firstparameter tolist.insert() assuming thata is already sorted.

The returned insertion pointi partitions the arraya into two halves sothatall(val<xforvalina[lo:i]) for the left side andall(val>=xforvalina[i:hi]) for the right side.

bisect.bisect_right(a,x,lo=0,hi=len(a))
bisect.bisect(a,x,lo=0,hi=len(a))

Similar tobisect_left(), but returns an insertion point which comesafter (to the right of) any existing entries ofx ina.

The returned insertion pointi partitions the arraya into two halves sothatall(val<=xforvalina[lo:i]) for the left side andall(val>xforvalina[i:hi]) for the right side.

bisect.insort_left(a,x,lo=0,hi=len(a))

Insertx ina in sorted order. This is equivalent toa.insert(bisect.bisect_left(a,x,lo,hi),x) assuming thata isalready sorted. Keep in mind that the O(log n) search is dominated bythe slow O(n) insertion step.

bisect.insort_right(a,x,lo=0,hi=len(a))
bisect.insort(a,x,lo=0,hi=len(a))

Similar toinsort_left(), but insertingx ina after any existingentries ofx.

See also

SortedCollection recipe that usesbisect to build a full-featured collection class with straight-forward searchmethods and support for a key-function. The keys are precomputed to saveunnecessary calls to the key function during searches.

8.6.1.Searching Sorted Lists

The abovebisect() functions are useful for finding insertion points butcan be tricky or awkward to use for common searching tasks. The following fivefunctions show how to transform them into the standard lookups for sortedlists:

defindex(a,x):'Locate the leftmost value exactly equal to x'i=bisect_left(a,x)ifi!=len(a)anda[i]==x:returniraiseValueErrordeffind_lt(a,x):'Find rightmost value less than x'i=bisect_left(a,x)ifi:returna[i-1]raiseValueErrordeffind_le(a,x):'Find rightmost value less than or equal to x'i=bisect_right(a,x)ifi:returna[i-1]raiseValueErrordeffind_gt(a,x):'Find leftmost value greater than x'i=bisect_right(a,x)ifi!=len(a):returna[i]raiseValueErrordeffind_ge(a,x):'Find leftmost item greater than or equal to x'i=bisect_left(a,x)ifi!=len(a):returna[i]raiseValueError

8.6.2.Other Examples

Thebisect() function can be useful for numeric table lookups. Thisexample usesbisect() to look up a letter grade for an exam score (say)based on a set of ordered numeric breakpoints: 90 and up is an ‘A’, 80 to 89 isa ‘B’, and so on:

>>>defgrade(score,breakpoints=[60,70,80,90],grades='FDCBA'):...i=bisect(breakpoints,score)...returngrades[i]...>>>[grade(score)forscorein[33,99,77,70,89,90,100]]['F', 'A', 'C', 'C', 'B', 'A', 'A']

Unlike thesorted() function, it does not make sense for thebisect()functions to havekey orreversed arguments because that would lead to aninefficient design (successive calls to bisect functions would not “remember”all of the previous key lookups).

Instead, it is better to search a list of precomputed keys to find the indexof the record in question:

>>>data=[('red',5),('blue',1),('yellow',8),('black',0)]>>>data.sort(key=lambdar:r[1])>>>keys=[r[1]forrindata]# precomputed list of keys>>>data[bisect_left(keys,0)]('black', 0)>>>data[bisect_left(keys,1)]('blue', 1)>>>data[bisect_left(keys,5)]('red', 5)>>>data[bisect_left(keys,8)]('yellow', 8)