4

Is there any pythonic way to find the first coincidence before a giving index?

For example I want to find the 2 that go before the 1, and the the 2 that go after the 1.

a = [0,2,0,0,1,0,0,2,0]

for the 2 that go after the 1 I use this a.index(2,4).

Is there any easy or clean way to do it?

exsnake
  • 1,767
  • 2
  • 23
  • 44

4 Answers4

4

You can reverse the list and calculate the index of your "pivot" element in the reversed list, then use index as normal:

def find_before(lst, e, idx):
    new_idx = len(lst) - idx - 1
    return len(lst) - lst[::-1].index(e, new_idx) - 1

It's worth noting that this is a bad idea for huge lists because it temporarily creates a copy when it reverses it. A better idea for that scenario is what blhsing did, which is just stepping backwards through the list:

def find_before(lst, e, idx):
    i = idx
    while i > 0:
        i -= 1
        if lst[i] == e:
        return i
    else:
        raise ValueError(f"No element {e} found before index {idx}")
MoxieBall
  • 1,907
  • 7
  • 23
2

You just have to do it yourself since there's no built-in function for the equivalent of str.rindex for lists:

def rindex(lst, x, start=-1, end=0):
    if start < 0:
        start += len(lst)
    i = start
    while i >= end and lst[i] != x:
        i -= 1
    if i < 0:
        raise ValueError()
    return i

a = [0,2,0,0,1,0,0,2,0]
print(rindex(a, 2, 4))

This outputs:

1
blhsing
  • 91,368
  • 6
  • 71
  • 106
1

In O(n) you can build a dict that holds all positions of any element of your list:

a = [0,2,0,0,1,0,0,2,0]

pos = {}

for idx, elem in  enumerate(a):
    pos.setdefault(elem,set())
    pos[elem].add(idx)    

print(pos) # {0: {0, 2, 3, 5, 6, 8}, 2: {1, 7}, 1: {4}}

Finding the position of one element is just one O(1) operation away:

print(pos[2])  # {1,7}

If you want the first and last occurence, you can do:

print(min(pos[0]),max(pos[0])  #  0 8

You can query other things as well:

# get index of first 2 that is before the 1st 1
print( min(x for x in pos[2] if x < min(pos[1])))  # 1

# get index of all 0s that are after the 1st 1
print( list(x for x in pos[0] if x > min(pos[1])))  # [5, 6, 8]

As for the 2 before 1st 1 and after 1st 1:

firstOneIdx = min(pos[1]) # calc min index of 1 before, so it is not recalc'ed
print( "2 before 1st 1:" , list(x for x in pos[2] if x < firstOneIdx))
print( "2 after  1st 1:" , list(x for x in pos[2] if x > firstOneIdx))

which outputs:

2 before 1st 1: [1]
2 after  1st 1: [7]

You can use min/max to reduce the lists to 1 element.

Patrick Artner
  • 50,409
  • 9
  • 43
  • 69
0

The answer can be broken down into three sub-operations: split the array into two sub-arrays and then search the first from the end and search the second from the beginning.

def index(array, value, pivot):

    def find(array):
        return array.index(value)

    first_half = arr[ (pivot - 1) : : -1 ]
    last_half = arr[ (pivot + 1) : ]
    return [ pivot - find(first_half) - 1, pivot + find(last_half) + 1 ]

In essence, this method splits your array around pivot and rearranges the first sub-array backwards. After that, you simply find the first occurrence of value in both, which corresponds to the closest occurrence of value to pivot in the array. It would work like this:

indexes = index(array, 2, 4)
# [1, 7]
Woody1193
  • 7,252
  • 5
  • 40
  • 90