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) == 2Related terms
- binary search — Finding a target in sorted data by comparing it with the middle item and throwing away the half where it cannot be.
- sorted list — A list kept in ascending order, which supports O(log n) search with binary search at the cost of O(n) insertion.
- range query — A request for every item whose key lies between two bounds, such as all orders placed between 9:00 and 10:00.
Taught in
- Binary Search And Its Invariant — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers