Efficiency of Python "in" keyword for sorted list

Question

If I have a list that is already sorted and use the in keyword, for example:

a = [1,2,5,6,8,9,10]
print 8 in a

I think this should do a sequential search but can I make it faster by doing binary search? Is there a pythonic way to search in a sorted list?

Answer 1

The standard library has the bisect module which supports searching in sorted sequences.

However, for small lists, I would bet that the C implementation behind the in operator would beat out bisect. You'd have to measure with a bunch of common cases to determine the real break-even point on your target hardware...

---

It's worth noting that if you can get away with an unordered iterable (i.e. a set), then you can do the lookup in O(1) time on average (using the in operator), compared to bisection on a sequence which is O(logN) and the in operator on a sequence which is O(N). And, with a set you also avoid the cost of sorting it in the first place :-).