Does Python's 'in' operator for lists have an early-out for successful searches

Question

If i have a list then i look up a element in list by:

alist=[ele1, ele2, ele3, ele4,ele5,...]
if ele3 in alist:
  print "found" 

Will in stop a search from alist at ele3 ? Or it will run though all remaining element to the end.

Thanks in advance!

Answer 1

Will in stop a search from alist at ele3 ?

Yes, the in operator on a list does a linear search with an early exit if the target is found. Also, it will by-pass the final comparison if the target object is identical to the object in the list.

Here's some tracer code that proves the result by making the comparisons visible:

class Int(int):
    'Make comparisons visible'
    def __cmp__(self, other):
        print 'Comparing %s to %d' % (self, other)
        return int.__cmp__(self, other)

ele1 = Int(1)
ele2 = Int(2)
ele3 = Int(3)
ele4 = Int(4)
ele5 = Int(5)

alist = [ele1, ele2, ele3, ele4, ele5]
if ele3 in alist:
  print "found" 

The output is:

Comparing 3 to 1
Comparing 3 to 2
found

Python translates the in operator in the expression ele3 in alist into a magic method call such as alist.__contains__(ele3). The list.__contains__() method works like this:

def __contains__(self, target):
    for element in self:
        if target is element or target == element:
            return True
    return False

Hope this makes the process crystal clear :-)