r/pythontips • • Feb 05 '23

Module Tip - Use Python Builtin Binary Search (Bisect) on Sorted List

Hello all,

As you might know, the most efficient way to search a sorted array in Python is using Binary Search which is logarithmic time as opposed to linear time in the brute force method. Doing operations on sorted lists is common practice in many coding interview questions.

If you are not asked to implement binary search from scratch I recommend everyone get familiar with how to use the bisect_left() method, which many people may not know about. This is essentially a built-in binary search implementation in Python as opposed to coding it from scratch. So if you need binary search and forgot how to implement it or do not have time to write it up, consider using this.

It is very simple to use and involves one line of import code (no need to pip install) and one line of implementation.

```

from bisect import bisect_left

index = bisect_left(array, goal)

```

This will allow you to find where the leftmost index of an item would be inserted in a sorted array. This can potentially save you time and keep your code cleaner.

If you have any more questions or thoughts on this method let me know below. I also have a youtube video that better shows the implementation:

https://youtu.be/iwVHbZa9NH8

***Note there is also the bisect_right method which is very similar but instead finds the rightmost index, however, it is much less commonly used.

28 Upvotes

4 comments sorted by

3

u/Machvel Feb 06 '23

how does the bisect library compare in speed to the sortedcontainers library? i use sortedcontainers for speed improvements for this type of thing, but am wondering if i might want to use bisect instead for some tasks

3

u/QuietRing5299 Feb 06 '23

That is a very interesting question. I never used sorted containers before but I just did an experiment with the two methods as follows.

Using the two methods

from sortedcontainers import SortedList

import timeit from bisect import bisect_left

sequence = list(range(0, 10000, 2)) sorted_container = SortedList(sequence)

def find_closest_bisect(sequence, goal):
index = bisect_left(sequence, goal)
return index

def find_closest_sortedcontainer(sorted_container, goal): index = sorted_container.index(goal) return index

First method is for the traditional bisect method shown in this post and the second is for the sorted container method. I ran a timeit on both functions as follows (1000 runs each):

binary_time = timeit.timeit(
stmt='find_closest_bisect(sequence, 9500)',
globals=globals(),
number=1000

) sorted_container_time = timeit.timeit( stmt='find_closest_sortedcontainer(sequence, 9500)', globals=globals(), number=1000 )

print(f'Time for bisect method {binary_time}') print(f'Time for sorted_container method {sorted_container_time}') print(f'Speedup bisect method over sorted container {sorted_container_time/binary_time}')

Output:
>>> Time for bisect method 0.00022945799999998795
>>> Time for sorted_container method 0.030982417000000012
>>> Speedup bisect method over sorted container 135.02434868255472

So it appears based on this method that bisect is much faster for finding the index of a goal value in a sorted array. Would be interesting to know if you think there are any weaknesses in this experiment, however.

7

u/primitive_screwhead Feb 05 '23

The example of using bisect to look up a range, given a specific value is <chef's kiss>:

https://docs.python.org/3.11/library/bisect.html#examples

2

u/dimonoid123 Feb 06 '23

You can also use similar technique on pandas data frames with time series.

O(log(n)) difficulty to find closest element.