Joe Mosby's blog

More high performance iterable work with bisect

In my last post, I explored the Python array data structure. In keeping with the vibe of iterable data structures, I'm moving on to cover the bisect module.

bisect uses a simple bisection algorithm to insert items into a list without botching the sort. The gist of the algorithm is simple: we're going to create a midpoint using the low and high marks of the list, check if our value is greater than or less than the midpoint, then use the midpoint to slice the list into smaller and smaller lists until our item falls right at the midpoint.

You can see this in action here:

def bisect_pseudo(a_list, my_value):
	low = 0
	high = len(a_list)

	while low < high:
		midpoint = (low+high)//2

		if my_value < a_list[midpoint]:
			high = midpoint
		else:
			low = midpoint + 1

		print "low:", low, "high", high

	return low

my_list = [1, 4, 9, 16, 25]

print "Value greater than midpoint: "
bisect_pseudo(my_list, 10)

print "Value less than midpoint: "
bisect_pseudo(my_list, 2)

In this example, we see the algorithm sifting through our list, searching for the point in the list where our test value would naturally slide in. This is a left bisection algorithm - where we start from the left side of the list and work up - and the reverse would be a right bisection algorithm. The bisect module includes both.

import bisect

names = ['Joe', 'Beth', 'Steve']

names.sort()

print names

print bisect.bisect_left(names, 'David')

bisect.insort_left(names, 'David')

print names

In this example, we're using the bisect_left() function, an implementation of the same algorithm described above, to find the midpoint in our sorted list. The insort_left() function will perform this algorithm and then insert our value exactly where it needs to be. The code using the right bisection algorithm looks similar:

print bisect.bisect_right(names, 'Shamyl')

bisect.insort_right(names, 'Shamyl')

print names

The Python bisect module is fairly quick, but it will use a faster C implementation if one's available. That's all there is to it!