How Can I Deep Search A Python List?

I want to deep search in a list in Python. For example, I want to know that 5 is in my_list or not. my_list = [2, [3, 4, [2, 3]], 1, [4, [5]]] How can I do that?

Solution 1:

Not sure a quick way to do this with multi-levels of nests, but a recursive algorithm like this would do the trick:

def nestedSearch(nested, v):
    for element in nested:
        if isinstance(element, list):
            if nestedSearch(element, v):
                return True
        elif element == v:
            return True
    return False

You also might look at this for flattening multi-nested lists:

Recursive generator for flattening nested lists

Solution 2:

You can combine the flatten function (think of it as a recursive version of itertools.chain) with Python's standard in operator (which, on generators, does a linear search) to get this:

>>> def flatten(nested):
    try:
        for sublist in nested:
            for element in flatten(sublist):
                yield element
    except TypeError:
        yield nested


>>> my_list = [2, [3, 4, [2, 3]], 1, [4, [5]]]
>>> 5 in flatten(my_list)
True

Per the comments in the linked question, you will want to refine the flatten code if what you're searching for is iterable - eg, tuples will be flattened into the search just like lists, and searching for strings recurses until it hits Python's stack limit.

Solution 3:

If you have a list of lists, you can use this approach

>>> l = [[1,2,3],[4,5,6], [7], [8,9]]
>>> [item for sublist in l for item in sublist]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> 5 in [item for sublist in l for item in sublist]
True

Which first flattens the list and the searches through it using O(n).

If your list looks like in your example, I can't think of another way to do it than using for-loops...

Solution 4:

One way for doing it:

def deapSearch(searchElement, searchList):
    for element in searchList:
        if element == searchElement:
            return True
        elif type(element) == type(list):
            found = deapSearch(searchElement, element)
            if found:
                return found
    return False
deapSearch(5, my_list)
True
deapSearch(4, my_list)
True

Not Beautiful but working.

Solution 5:

I recently needed to do this and needed a simple solution. So I am adding it as an a quick and dirty way to flatten/search a list (may not be a perfect solution but it worked for me).

>>> my_list = [2, [3, 4, [2, 3]], 1, [4, [5]]]
>>> str(5) in str(my_list) # returns True
>>> str(my_list).find(str(5)) # returns the index

Edit: Adding a regex solution as well. But if you have a more complicated case, then you might as well traverse the list.

>>> import re
>>> str(5) in re.findall('(?<=[,\[])([ a-zA-Z0-9 ]+)(?=[,\]])', str(my_list))

The regular expression essentially flattens the list, but won't work for special characters in list items.