bisect module

Python's standard-library module of correct binary-search functions for sorted lists.

In more detail

bisect_left returns the first position where a value could be inserted to keep order, and bisect_right the position just past any equal values. insort finds that position and inserts there, but the insertion itself shifts elements and costs O(n). Using bisect avoids hand-written off-by-one bugs.

Example

bisect.bisect_left([1, 3, 5, 5, 7], 5) == 2

Related terms

Taught in

References