CODEWITHSUNDEEP
python-3.xlist
Sachin Negi
Sachin Negi

Reputation: 1

which searching method is used by element in list in python

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)

Upvotes: 0

Views: 393

Answers (2)

Thomas
Thomas

Reputation: 721

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."

Upvotes: 2

Green Cloak Guy
Green Cloak Guy

Reputation: 24691

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).

Upvotes: 2

Related Questions