Algorithm used by keyword 'in'

[Josiah Carlson]

> 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