How can I deep search a Python list?

Question

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?

Answer 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

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

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

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

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

Answer 6

if you only have a nested list with integers or chars, one way to solve this problem is to create a list without all unwanted elements ( without '[' , ']' ... ) :

let's say we have a nested list with chars :

>>> nested = [[[[['F', 'B'], 'G'], ['D', 'A']], 'C'], 'E']
>>> string = str(nested)
>>> string = string.replace('[','',len(string))
>>> string = string.replace(']','',len(string))
>>> string = string.replace("'","",len(string))
>>> string = string.replace(" ","",len(string))
>>> string = string.split(',')

it gives :

>>> print (string)
['F', 'B', 'G', 'D', 'A', 'C', 'E']

Now you can search easily without any loop :

>>> 'F' in string
True