0

I'm trying to find if an number is in the given list but can't figure it out.

I figured out how to do this with just a list(not nested):

def find(lst, number):
    if len(lst) == 0: #base case
        return False
    else:
        return number in lst

But the problem is with a nested list the above code won't work

What I have so far:

def find(lst, number):
    if len(lst) == 0:
        return False
    else:
        for i in lst:
            if isinstance(i, list):
                for item in i:
                    if item == number:
                        return True
            elif i == number:
                return True
            else:
                continue

# Nested List (What it should output).
>>> find([1, [3, [4 , [7, 8]], 9]], 8)
True
Sc4r
  • 700
  • 1
  • 10
  • 15
  • 3
    Why do you have the `base case` comment in a non-recursive algorithm? Further, why do you have that line at all? `return number in lst` works fine with an empty list. – user2357112 Feb 02 '14 at 03:49
  • Your real problem is flattening an irregular nested list; see the dupe. – Martijn Pieters Feb 02 '14 at 03:50
  • lazy (and wrong) way: Convert list to string, remove all `[` and `]`, `eval` it and check `number in the_list` – JBernardo Feb 02 '14 at 03:51
  • 3
    While this can be done by flattening, I wouldn't consider it a dupe of a question about flattening. – user2357112 Feb 02 '14 at 03:51
  • 1
    @user2357112 No matter how you much you try, you will need to flatten the list or at least walk through it as if it were flatten. – JBernardo Feb 02 '14 at 03:54
  • @JBernardo: at least use `ast.literal_eval()` then. :-P – Martijn Pieters Feb 02 '14 at 03:58
  • @JBernardo You need to walk through all the lists. You do not need to flatten it or pretend it's flattened. – nos Feb 02 '14 at 04:01
  • @MartijnPieters But then I would not win a code golf contest – JBernardo Feb 02 '14 at 04:03
  • @JBernardo: Would you consider the other question a dupe of this one if the other question were posted two months after now? If not, I wouldn't consider this one a dupe; the relation is symmetric. Also, off the top of my head, BFS would solve the problem without flattening the list or walking through it as if it were flattened. – user2357112 Feb 02 '14 at 04:04
  • @user2357112 The other question has all the information needed to solve this problem. Also, if you read the answers below, they are all worse than the best answer from the other question. (And you indeed flattened the list) – JBernardo Feb 02 '14 at 04:06

4 Answers4

1

Use recursion:

def find(lst, number):
    for item in lst:
        if item == number:
            return True
        elif isinstance(item, list) and find(item, number):
            return True
    return False

The key part is here:

        elif isinstance(item, list) and find(item, number):

If the list element is another list, the algorithm calls itself to determine whether the number is in the sublist. This avoids needing to write nested for loops for each of the infinitely many possible levels of nesting the list could have.

user2357112
  • 260,549
  • 28
  • 431
  • 505
1

Rather than writing out an explicit loop, you could the built in any function on a generator expression:

def find(lst, num):
    return any(x == num or (isinstance(x, list) and find(x, num)) for x in lst)

Or an alternative version that checks the top level list first, before recursing with any:

def find2(lst, num):
    return num in lst or any(find2(x, num) for x in lst if isinstance(x, list))

any short circuits if it finds a True value, so it should be relatively fast, and it already has the right behavior for empty lists (any([]) returns False) so you don't need any special cases.

Blckknght
  • 100,903
  • 11
  • 120
  • 169
0
def find_recursive(num, lst):   
    if isinstance(lst, int):
        return num == lst
    elif not lst:
        return False        
    else:
        first = lst[0]
        rest = lst[1:]
        return find_recursive(num, first) or find_recursive(num, rest)

print(find_recursive(7, [8, [3, [4 , [7, 8]], 9]])) # prints True
print(find_recursive(1, [8, [3, [4 , [7, 8]], 9]])) # prints False
Nir Alfasi
  • 53,191
  • 11
  • 86
  • 129
0

You can use recursion, that is, replace this piece:

if isinstance(i, list):
    for item in i:
        if item == number:
            return True

with:

if isinstance(i, list):
    if find(i, number:
        return True
nos
  • 223,662
  • 58
  • 417
  • 506