Python bisect module
The Bisect Module
The bisect module in Python provides two main functions, bisect_left() and bisect_right(), which operate on a sorted list and return the position where the target value can be inserted to maintain the order of the list. The bisect_left() function returns the leftmost position where the target value can be inserted, while bisect_right() returns the rightmost position.
The bisect module in Python provides support for binary search algorithms. It is a built-in module that allows us to perform binary searches on sorted lists in an efficient manner. In this blog post, we will be demonstrating the use of the bisect module with a simple example.
#!/usr/bin/env python
import random
import timeit
from bisect import bisect_left
size = 10 ** 5
iterations = 1000
eg_data = list(range(size))
eg_to_lookup = [random.randint(0, size) for _ in range(iterations)]
def run_linear(data, to_lookup):
for index in to_lookup:
data.index(index)
def run_bisect(data, to_lookup):
for index in to_lookup:
bisect_left(data, index)
if __name__ == '__main__':
baseline = timeit.timeit(stmt='run_linear(eg_data, eg_to_lookup)',
globals=globals(), number=10)
print(f'Linear search takes {baseline:.6f}s')
comparison = timeit.timeit(stmt='run_bisect(eg_data, eg_to_lookup)',
globals=globals(), number=10)
print(f'Bisect search takes{comparison:.6f}s')
slowdown = 1 + ((baseline - comparison) / comparison)
print(f'{slowdown:.1f}x time')