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?
-
1possible duplicate of Binary Search in PythonMatt Ball– Matt Ball2014-05-10 06:29:41 +00:00Commented May 10, 2014 at 6:29
-
Good question - It would be good to know how the search is conducted in sorted(my_list) too.Reblochon Masque– Reblochon Masque2014-05-10 06:30:42 +00:00Commented May 10, 2014 at 6:30
-
1It'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– pah2014-05-10 06:35:07 +00:00Commented May 10, 2014 at 6:35
-
@ threadp: not quite true. See below.hivert– hivert2014-05-10 06:56:16 +00:00Commented May 10, 2014 at 6:56
Add a comment
|
2 Answers
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.
answered May 10, 2014 at 6:45
Martijn Pieters
1.1m326 gold badges4.2k silver badges3.4k bronze badges
3 Comments
hivert
@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
@MartijnPieters not on my machine... You should definitely check on yours.
Martijn Pieters
@hivert: ah, no, I was indeed forgetting the
elem > self[-1] case. Thanks for pointing that out. Corrected.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