Algorithm used by keyword 'in'

Josiah Carlson jcarlson at uci.edu
Sat Oct 9 21:18:09 CEST 2004


> Is python smart enough to do say a binary search if you sort the list 
> right before using in?

No, use the bisect module if you want to binary search.  Knowing that a
sequence is sorted requires keeping an 'is_sorted' boolean attached to
the object (which may end up increasing the space used by each list).

It is also ambiguous to say that a list is "sorted".  Even if the
following passes without exception:

for i in xrange(len(lst)-1):
    assert lst[i] < lst[i+1]

That does not mean that there isn't an ambiguous ordering that would
make binary search and/or list.sort() incorrect:
>>> 'b' < (0,)
True
>>> (0,) < u'a'
True
>>> u'a' < 'b'
True

One should need to be explicit when they want to binary search, because
it may not be correct in some cases.

"In the face of ambiguity, refuse the temptation to guess."


 - Josiah




More information about the Python-list mailing list