python implicit binary search

Question

I have list which is already sorted.

I often need to check to see

if foo in sortedlist:
    pass  # not really.  but not the point.

Is there a way to teach 'in' that sortedlist is sorted and that it should binary search the list?

Answer 1

Python favours explicit over implicit. Your options are to explicitly use the bisect module if you know your data is sorted, or create a subclass of list that implements __contains__ by using that module.

For example:

import bisect


class SortedList(list):
    def __contains__(self, elem):
        idx = bisect.bisect_left(self, elem)
        return idx < len(self) and self[idx] == elem

could be used as a substitute for list, and in will use __contains__ automatically. You'd probably want to override __setitem__, .extend() and .append() to maintain the list in sorted order, too.

Answer 2

My suggestion would be to subclass list to use sorted list:

from bisect import bisect_left
class SortedList(list):
    def __init__(self, l):
        list.__init__(self, sorted(l))
    def __contains__(self, obj):
        pos = bisect_left(self, obj, 0, len(self))
        return (pos != len(self) and self[pos] == obj)

Then:

>>> l = SortedList([4,3,5435,123,54,2,343,23])
>>> l
[2, 3, 4, 23, 54, 123, 343, 5435]
>>> 23 in l
True
>>> 25 in l
False
>>> 123122 in l
False
>>> -1 in l
False