The bisect module offers two main functions - bisect and insort - that use the binary search algorithm to quickly find an d insert items in any sorted sequence.

Searching with bisect

bisect(haystack, needle) does a binary search for needle in haystack, which must be sorted.

bisect is actually an alias for bisect_right, and there is a sister function named bisect_left. Their difference is apparent only when the needle compares equal to an item in the list: bisect_right returns an insertion pointer after the existing item, while bisect_left returns the position of the existing item, so insertion would occur before it.

import bisect

haystack = [1,4,4,5,6,8,12]
needles = [0,1,2,4,8,10]

for n in needles:
    l = bisect.bisect_left(haystack, n)
    r = bisect.bisect(haystack, n)

    """
    0 0
    0 1
    1 1
    1 3
    5 6
    6 6
    """
    print(l, r)

The bisect() function can be useful for numeric table lookups. This example uses bisect() 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 is a ‘B’, and so on:

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    i = bisect(breakpoints, score)
    return grades[i]

# ['F', 'A', 'C', 'C', 'B', 'A', 'A']
[grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]

Inserting with bisect.insort

insort(seq, item) inserts item to seq so as to keep seq in ascending order.

import bisect
import random

SIZE = 7
random.seed(1902)

lst = []
for _ in range(SIZE):
    item = random.randrange(SIZE*2)
    bisect.insort(lst, item)
    print('%2d -> ' % item, lst)

The output of above code is:

 0 ->  [0]
 0 ->  [0, 0]
 7 ->  [0, 0, 7]
 8 ->  [0, 0, 7, 8]
12 ->  [0, 0, 7, 8, 12]
 7 ->  [0, 0, 7, 7, 8, 12]
 3 ->  [0, 0, 3, 7, 7, 8, 12]

Reference

Fluent Python