One unique feature of Python is the availability of various libraries and modules, which make it easy for developers. In this article, we are going to learn about the Bisect module, which provides a set of functions for working with sorted lists in Python. We will also learn about Bisect left & right, the key, how it works, and its time complexity.
What is Bisect in Python?
Python's Bisect module works on ordered lists, allowing you to easily find the index at which a new value should be inserted to maintain the order of the list. When working with large datasets or searching for a specific value in a sorted list, Bisect can be very useful.
With Bisect, you can avoid the use of complicated search algorithms, which saves time and effort, helps you write better code, and is less time-consuming.
If you're new to programming, you may be wondering what an ordered list is. An ordered list is simply a list of items that have been sorted into a specific order. For example, you might have a list of numbers that are sorted in ascending order (smallest to largest) or a list of words that are sorted alphabetically.
Is bisect built-in in Python? Yes, Bisect is a built-in module, you do not need to install any external libraries to use it in your code.
The bisect module has two main functions: bisect and insert. The bisect function is used to find the position in a sorted list where a new item should be inserted, while the insert function is used to insert a new item into a sorted list while maintaining the sort order.
Let's now have a simple example to better understand it:
import bisect Names = ['alex','lucky','maya','tushar'] new_name = 'shaina' index = bisect.bisect(names, new_name ) print(f"The index where {new_name} should be inserted is {index}")
Here, we import the bisect module and define a sorted list called names and a target value called new_name. We then use the bisect function to find the index where Shaina should be inserted into names. The output of this code will be:
Output:
The index where shaina should be inserted is 3
Let us now understand how the insert function works by considering the below example:
import bisect names = ['alex','lucky','maya','tushar'] new_name = 'shaina' bisect.insert(names, new_name ) print(names)
Here, we import the bisect module and define a sorted list called names and a target value called new_name. We then use the insert function to find the insert where Shaina or new_name should be inserted into names.
Output:
['alex', 'lucky', 'maya', 'shaina', 'tushar']
How Bisect Works?
Bisect in Python makes use of the binary search algorithm to efficiently search for a target value in a sorted list.
A binary search is a search algorithm that runs on sorted data. The middle element of the sorted data is compared to the target value in binary search. The search is terminated if the middle element equals the target value.
If it isn't equal then the target value is compared to the middle element, if it is smaller than the middle element, the search is resumed in the data's left half or If the target value is greater than the middle element then the search is to the right half. The search will continue until the target value is found or there are no more elements to find.
Python's Bisect Time Complexity
Since it uses a binary search algorithm to find the correct index to add a new element or search for an existing element in a sorted list, the time complexity of the bisect module in Python is O(log n).
This makes the task much more efficient than individually scanning over each element in the list, especially for large lists.
What is bisect left & bisect right?
bisect_left and bisect_right are functions provided by the bisect module in Python for searching for an element in a sorted list.
The bisect left function returns the index of the sorted list where the element should be added to maintain the list in order. If the element already exists in the list, bisect left will return the index of the element's first occurrence.
In contrast, the bisect right function returns the rightmost index in the sorted list where the element should be put. If the element is already present in the list, bisect_right will return the next index after the last occurrence of the element.
Both take 2 parameters: the ordered list that is to be searched and the element to search for.
Let us understand left bisect via an example:
import bisect old_list = [1,2,3,4,4,5] target = 4 left = bisect.bisect_left(old_list,target) if left < len(old_list) and old_list[left] == target: print("Found element at index",left) else: print("Element not found in list") right = bisect.bisect_right(old_list,target) if right < len(old_list) and old_list[right-1] == target: print("Found element at index",right-1) else: print("Element not found in list")
Output:
Found element at index 3 Found element at index 4
What is the Python bisect key?
In addition to the bisect_left and bisect_right functions, the bisect module also provides a bisect function that takes a list, a target value, and an optional key function as input. Instead of the items themselves, we may need to search/insert values based on some key associated with each member in the list.
In such circumstances, we may use the bisect function's key option to define a function that will be used to extract the key value from each element in the list.
Let us look at the tuple “names” and consider this example:
Code 4 import bisect names = [(1, "alex"), (3, "maya"), (5, "abrar")] # key function to extract the first element of each tuple (the integer) key_func = lambda x: x[0] # search for the index where the value 6 should be inserted index = bisect.bisect(names, 6, key=key_func) print(f"the index where 6 can be inserted is {index}")
Output:
the index where 6 can be inserted is 3
Conclusion
Overall, Bisect is a useful module within python that can help you optimize the performance of your code. Whether you are working on a data analysis project or developing a web application, the next time you're dealing with a sorted list in Python, think about utilizing the bisect module.
