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?

possible duplicate of [Binary Search in Python](http://stackoverflow.com/questions/212358/binary-search-in-python) — Matt Ball, May 10 '14 at 06:29
Good question - It would be good to know how the search is conducted in sorted(my_list) too. — Reblochon Masque, May 10 '14 at 06:30
It's not possible to change the behavior of 'in'. What you're looking for is the the link pointed by Matt Ball (possible duplicate). — pah, May 10 '14 at 06:35

Martijn Pieters · Accepted Answer · 2014-05-10T07:06:19.337

4

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.

edited May 10 '14 at 07:06

answered May 10 '14 at 06:45

Martijn Pieters

1,048,767
296
4,058
3,343

@MartijnPieters: your code is not correct: It raise a `IndexError: list index out of range` if elem is larger than the largest element of the list: the returned `idx` is `len(self)`. – hivert May 10 '14 at 06:55
@MartijnPieters not on my machine... You should definitely check on yours. – hivert May 10 '14 at 07:06
@hivert: ah, no, I was indeed forgetting the `elem > self[-1]` case. Thanks for pointing that out. Corrected. – Martijn Pieters May 10 '14 at 07:06

score 2 · Answer 2 · answered May 10 '14 at 06:53

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

python implicit binary search

2 Answers2