Python bisect module demo
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')
The bisect module in Python provides support for efficient binary searches on sorted lists. It allows us to find the position where a target value can be inserted to maintain the sorted order of a list. This can be useful in a variety of applications, such as searching for values in large datasets or implementing sorting algorithms. We hope this demo has been helpful in demonstrating the use of the bisect module in Python.
