which searching method is used by element in list in python

Question

When I use the function to check if element is present in list in python by using element in List. Which searching method is used in the background. ex 2 in [2,3,4,5]

for example in the following code:

list=[2,3,4]
if 2 **in** list:
     print(True)
else:
     print(False)

Possible duplicate of [What does \_\_contains\_\_ do, what can call \_\_contains\_\_ function](https://stackoverflow.com/questions/1964934/what-does-contains-do-what-can-call-contains-function) — Andrej Kesely, Jul 30 '19 at 14:13
why does it matter? Have you read the [docs](https://docs.python.org/3/reference/expressions.html#membership-test-details) — depperm, Jul 30 '19 at 14:17
I think knowing the method used in the background doesn't do any harm, and I was curious about it — Sachin Negi, Jul 30 '19 at 14:22
Its just a linear search because lists are not normally sorted. If it is sorted you can use `bisect` for binary searching. — Error - Syntactical Remorse, Jul 30 '19 at 14:26
@Error-SyntacticalRemorse thanks I had doubt that it used binary search. — Sachin Negi, Jul 30 '19 at 14:31

score 2 · Answer 1 · answered Jul 30 '19 at 14:17

Here's the code for the implemention in cpython:

static int
list_contains(PyListObject *a, PyObject *el)
{
    Py_ssize_t i;
    int cmp;

    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
        cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
                                           Py_EQ);
    return cmp;
}

So as you can see, it's literally just walking through the list from front to back until the requisite element is found. The simplest possible algorithm for something like this. This checks out with the time complexity guide, which says that x in list has O(n) complexity.

Dicts and sets use a wholly different algorithm, because they're hash tables, a completely different data structure. Said different algorithm is almost always more efficient. If you're curious, you can also look at the source codes for sets and dicts respectively (the latter is much more complicated than the former, it looks like).

Thomas · Answer 2 · 2019-07-31T01:41:40.150

The in keyword can be used in different ways, but in this case, it's used to check if something contains something else. According to a documentation page about this, the in keyword calls __contains__, i.e.: x in y is the same as y.__contains__(x).

If SomeType.__contains__ is not defined by SomeType...

...the membership test first tries iteration via __iter__(), then the old sequence iteration protocol via __getitem__().

This would most likely be in linear time (O(n)). I say "most likely" because it depends on those implementations.

The in-built list type can have elements of different types and is not typically sorted, making binary search impossible (or at least illogical) and therefore, as stated by Green Cloak Guy, the CPython implementation performs the check linearly.

To answer the question in one term, it would be: "Linear Search."

which searching method is used by element in list in python

2 Answers2