Algorithm used by keyword 'in'

Chris Connett chrisconnett at
Sun Oct 10 00:41:31 CEST 2004

"Derek Rhodes" <rhoder at> wrote in message news:<lYS9d.144800$Kt5.79976 at>...
> #using python 2.4a3
> say there is a list:
> list = range(10000)
> Now randomize it.
> Next, command the interpreter:
> >>>  465 in list
>  True
> >>>
> What algorithm is used here?

Since there are no guarantees about the list or the items it contains,
the best list can do is a linear search.  Do be aware however that
each class can implement it's own behavior for keyword ``in``, by
implementing the ``__contains__`` method.  For example, sets and dicts
use a hash table implementation for their __contains__ method, so
performance there will be O(1), but sets and dicts can only contain
hashable items.  Your classes can implement it however they want, with
whatever semantics you want.

Chris Connett

More information about the Python-list mailing list