bisect module

The bisect module provides functions that help maintain lists in order without doing full sorting after each insertion.

It is also useful for searching in a sorted list. Search is done in logarithmic time, so it's better than linear search.

bisect.bisect_left(a, x) returns the insertion point for x in a. If values of x are already inserted in returns the position to the left of the first instance of x.

bisect.bisect_right(a, x) (same as bisect.bisect) returns the insertion point for x in a. If values of x are already inserted in returns the position of the right of the last instance of x.

bisect.insort_left(a, x) calls bisect.bisect_left to get the insertion position and then calls a.insert.

bisect.insort_right(a, x) calls bisect.bisect_right to get the insertion position and then calls a.insert.

Source