Background
You would have often come across a use case of finding an element in a sorted list. Typically you would use a binary search which takes O(logN). Python provides a module that does that for us - it is called bisect. The methods in this API allow us to find a position in the sorted list where a new element can be inserted to keep the lost sorted. In this post, we will explain how to use this module.
Understanding Bisect module in Python
Let's try to see the method bisect_left that gives us a position in a sorted list where a new element can be inserted to keep the list in sorted order. The syntax is
- bisect_left(list, element , low, high)
The arguments are
- list - a sorted list where we want to find the element to be inserted
- element - The element to be inserted
- low - the starting index of the list from where we want to start the search
- high - the ending index of the list from where we want to end the search
See the "Related links" section at the end for the official documentation link.
Now let's see an example
1 2 3 4 5 6 7 | import bisectlist = [1, 3, 5, 9, 10 ,15]idx = bisect.bisect_left(list, 6)print(f"Index to insert 6 is {idx}")list.insert(idx, 6)print(f"New list {list}") |
Above code prints:
Index to insert 6 is 3
New list [1, 3, 5, 6, 9, 10, 15]
You can also do both of the steps shown above - getting the index to be inserted for maintaining sorting and inserting it into the list in a single API provided by bisect. The API is
- insort_left(list, element)
Let's see how we can use above API to achieve the same result
1 2 3 4 5 | import bisectlist = [1, 3, 5, 9, 10 ,15]bisect.insort_left(list, 6)print(f"New list {list}") |
Output is: New list [1, 3, 5, 6, 9, 10, 15]
NOTE: bisect_left as the name suggests gives the left-most possible index to insert, whereas there is a similar API called bisect_right that gives the right-most possible index to insert. Similarly to insort_left we also have insort_right that does in place insertion of given element in given list.
Let's see an example of the above
1 2 3 4 5 6 7 | import bisectlist = [1, 3, 5, 5, 5, 9, 10 ,15]idx = bisect.bisect_left(list, 5)print(f"Left most index to insert 5 is {idx}")idx = bisect.bisect_right(list, 5)print(f"Right most index to insert 5 is {idx}") |
Above code prints:
Left most index to insert 5 is 2
Right most index to insert 5 is 5
NOTE: Time complexity is O(logN) which is the same as that of binary search.
We can actually use this API for multiple use-cases, let's see them below
1. Binary Search
As we say above you can use bisect to implement binary search.
1 2 3 4 5 6 7 8 9 10 11 | import bisectdef binary_Search(arr, element, low, high): idx = bisect.bisect_left(arr, element, low, high) if idx < len(arr) and arr[idx] == element: return idx return -1arr = [1, 3, 5, 7, 12, 20]search_idx = binary_Search(arr, 7, 0, len(arr))print(f"Binary search index for 7 : {search_idx}") |
Output is: Binary search index for 7 : 3
2. Prefix search
If your list had all strings (lower case) and in sorted order then we can use bisect for prefix search as well as follows:
1 2 3 4 5 6 7 8 9 10 11 | import bisectdef prefix_search(arr, prefix): idx = bisect.bisect_left(arr, prefix) if idx >= len(arr): return None el = arr[idx] return el if el.startswith(prefix) else Nonearr = ["apple", "cat", "dog","elephant"]print(prefix_search(arr, "ap")) |
Output is: apple
3. Find no of repeating values
If you have a sorted array and you want to find the number of times a number is repeated then we can use bisect again. Note that since the array is sorted the number will be sequential.
1 2 3 4 5 6 7 8 9 10 11 12 | import bisectdef count_repeated_no(arr, no): left_idx = bisect.bisect_left(arr, no) right_idx = bisect.bisect_right(arr, no) if left_idx >= len(arr): return -1 else: return right_idx - left_idxarr = [1, 2, 5, 5, 5, 5, 9, 1]print(f"Count of 5 in array {count_repeated_no(arr, 5)}") |
Output: Count of 5 in array 4
Performance
Note that this API is really fast.
- One because it uses binary search so it's time complexity is O(LogN)
- Secondly, it's precompiled in C so it's faster than if you implement it yourself (See SO question on comparison with direct lookup in list)
