The bisect module is used to locate positions in a sorted list and insert elements while maintaining order. It works using binary search and helps determine where a value fits within an existing sorted sequence.
The bisect module mainly offers two types of functionalities, as listed below:
Finding Insertion Points
These functions return the index at which the new element should be inserted to maintain the list's sorted order.
1. bisect.bisect(): Returns the rightmost insertion point for the element. If the element already exists, the insertion point will be after the existing entries.
bisect.bisect(list, num, beg=0, end=len(list))
Parameters:
- list: Sorted list.
- num: Element to insert.
- beg (optional): Start index for searching.
- end (optional): End index for searching.
Example: In this example, we find the rightmost position where the value 4 should be inserted in a sorted list.
import bisect
li = [1, 3, 4, 4, 6]
print(bisect.bisect(li, 4))
print(bisect.bisect(li, 4, 0, 3))
Output
4 3
Explanation:
- bisect(li, 4) returns 4 because insertion happens after last 4
- bisect(li, 4, 0, 3) searches in sublist [1, 3, 4] and returns 3
2. bisect.bisect_left(): Returns the leftmost insertion point for the element. If the element exists, the insertion point will be before the existing entries.
bisect.bisect_left(list, num, beg=0, end=len(list))
Example: Here, we find the leftmost position where the value should be inserted.
import bisect
li = [1, 3, 4, 4, 6]
print(bisect.bisect_left(li, 4))
print(bisect.bisect_left(li, 5))
Output
2 4
Explanation:
- bisect_left(li, 4) returns 2 (before first 4)
- bisect_left(li, 5) returns 4 (correct position for 5)
3. bisect.bisect_right(): Identical to bisect.bisect(), returns the rightmost insertion point.
bisect.bisect_right(list, num, beg=0, end=len(list))
Example: In this code, we find the rightmost insertion position similar to bisect().
import bisect
li = [1, 3, 4, 4, 6]
print(bisect.bisect_right(li, 4))
print(bisect.bisect_right(li, 4, 0, 4))
Output
4 4
Explanation:
- bisect_right(li, 4) returns 4 (after last 4)
- bisect_right(li, 4, 0, 4) works on [1, 3, 4, 4] and returns 4
Inserting Elements
These functions insert the element at the proper position to maintain sorting.
1. bisect.insort(): Inserts the element at the rightmost position. Unlike bisect() functions, this actually modifies the list by inserting the element.
bisect.insort(list, num, beg=0, end=len(list))
Example: Here, we insert a new value into the list while keeping it sorted.
import bisect
li = [1, 3, 4, 6]
bisect.insort(li, 5)
print(li)
Output
[1, 3, 4, 5, 6]
Explanation: insort(li, 5) inserts 5 at correct sorted position
2. bisect.insort_left(): Inserts the element at the leftmost position.
bisect.insort_left(list, num, beg=0, end=len(list))
Example: In this example, we insert a value at the leftmost valid position.
import bisect
li = [1, 3, 4, 4, 6]
bisect.insort_left(li, 4)
print(li)
Output
[1, 3, 4, 4, 4, 6]
Explanation: insort_left(li, 4) inserts 4 before existing 4s
3. bisect.insort_right(): Inserts the element at the rightmost position (similar to insort()).
bisect.insort_right(list, num, beg=0, end=len(list))
Example: Here, we insert a value at the rightmost position within a given range.
import bisect
li = [1, 3, 4, 4, 6]
bisect.insort_right(li, 5, 0, 4)
print(li)
Output
[1, 3, 4, 4, 5, 6]
Explanation:
- insort_right(li, 5, 0, 4) inserts 5 in sublist [1, 3, 4, 4]
- Value is placed at index 4, keeping list sorted
Why do we need Bisect Module?
- Useful for binary search operations to search in a sorted list and to locate insertion points.
- Provides efficient methods to insert elements into a sorted list while maintaining order.
- Avoids the need for manual sorting after each insertion, saving time and effort.
- Offers functions like bisect(), bisect_left(), bisect_right() and insort() for clean optimized code.
- Ideal for tasks like maintaining leaderboards, ranked data or any scenario involving sorted data insertion/search.