Bisect. Suppose you want to keep a list sorted in Python. You could repeatedly sort it after adding an item at the end, or you could call insort() from the bisect module.
With insort, an element is inserted in sorted order. The list must be already sorted—internally, the bisect() method is used to determine the insertion point.
Example. Here we use the bisect module in various ways. Generally with bisect, the insort() method is most important—it internally calls bisect on its own.
Step 1 It is important to call insort() on an already-sorted list. An empty list has no values, so it is considered sorted.
Step 2 With bisect_left, we can find the index of an existing element if one exists (otherwise, the insertion point is returned).
Step 3 We call insort() again, and it places the value -1 at the first index in the list.
Step 4 We can specify a key to keep the list sorted upon. We add tuples to the list, and specify (with a lambda) the second item in the tuples.
import bisect
# Step 1: create an empty list and add 3 integers in sorted order.
values = []
bisect.insort(values, 5)
bisect.insort(values, 1)
bisect.insort(values, 10)
print(values)
# Step 2: find the index of the value 4 within the sorted list.
position = bisect.bisect_left(values, 5)
print(position, values[position])
# Step 3: insert another value in sorted order.
bisect.insort(values, -1)
print(values)
# Step 4: create new list of tuples, and keep sorted by the second tuple item.
tuples = []
bisect.insort(tuples, ("bird", 10), key=lambda x: x[1])
bisect.insort(tuples, ("ant", 20), key=lambda x: x[1])
bisect.insort(tuples, ("apple", 0), key=lambda x: x[1])
print(tuples)[1, 5, 10]
1 5
[-1, 1, 5, 10]
[('apple', 0), ('bird', 10), ('ant', 20)]
Summary. With the bisect module, we have useful methods for binary search—we can call bisect to find insertion points for an element to keep a list sorted as we go along.
Dot Net Perls is a collection of pages with code examples, which are updated to stay current. Programming is an art, and it can be learned from examples.
Donate to this site to help offset the costs of running the server. Sites like this will cease to exist if there is no financial support for them.
Sam Allen is passionate about computer languages, and he maintains 100% of the material available on this website. He hopes it makes the world a nicer place.