1

I want to find the first index in A that contains a value from B. For example: 

A = [1, 'Q', 3, 6, 'R']
B = ['Z', 'I', 'O', 3]
A.function(B)  # would return 2

Is there a simple way of doing this? Obviously you can search through A for each item in B and take the minimum index, but this is slower than trying all of B for each index.

jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
Dr. John A Zoidberg
  • 1,168
  • 2
  • 14
  • 25
  • It depends which list is longer, as to whether finding the index of each item and taking the minimum is faster than searching through `B` on item at a time and seeing if it's in `A`. – jonrsharpe Jul 06 '16 at 09:07
  • finding the index of each item is O(A*B) always. the second method is O(A*B) in the worst case and O(1) in the best case. – Dr. John A Zoidberg Jul 06 '16 at 09:09

2 Answers2

4

I think there are two broad approaches, depending on which list is longer:

  1. A is longer than B:

    Take one item in A at a time and see if it's in B. Repeat until you find the first one that is.

    next(index for index, item in enumerate(A) if item in B)

    This is more efficient if B is converted to a set (thanks @khelwood), but be sure to do that before you start, not inside the generator expression.

  2. B is longer than A:

    Find the index in A of every item in B, then minimise:

    indices = []
for item in B:
    try:
        indices.append(A.index(item))
    except ValueError:
        pass
min(indices)

    Note that you cannot use:

    min(index for index in map(A.index, B) if index > -1)

    (oops!) because list doesn't have a method to get an index without an error (see e.g. list.index() function for Python that doesn't throw exception when nothing found).

Community
  • 1
  • 1
jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
0

The simplest way to do this is to iterate over every element of the first list, and check if each is in the second list.

def firstInBoth(A, B):
    for x in range(len(A)):
        if A[x] in B:
            return x
Aaron
  • 1
  • 1