r/pythontips • u/QuietRing5299 • 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:
***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.
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>:
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.
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