On Wed, Jun 9, 2010 at 11:54 PM, Benjamin Kaplan <benjamin.kap...@case.edu> wrote: > On Wed, Jun 9, 2010 at 10:25 PM, Qijing Li <qjing...@gmail.com> wrote: >> Thanks for your reply. >> I'm trying to understand python language deeply and use it efficiently. >> For example: How the operator "in" works on list? the running time is >> be O(n)? if my list is sorted, what the running time would be? >> >> > > Still O(n). Python doesn't know that your list is sorted, so nothing > changes. And the check to make sure it is sorted would be O(n) anyway.
However, if the programmer knows that the list is sorted, then the following would be O(log n): from bisect import bisect_left index = bisect_left(the_list, item) item_in_list = index < len(the_list) and the_list[index] == item But in general, if you want the "in" operator to be efficient, then you probably want to use a set or a dict, not a list. Cheers, Ian -- http://mail.python.org/mailman/listinfo/python-list
