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**