Find values in a list that are equal to the index they are in. How to optimize?

Question

I am learning programming with Python 3.6 and participate in a challenge site.

I need to find the smallest number whose value corresponds to its index in a list. If the list contains only one element, it should return the same. If there is more than one element that meets the criterion, it must return 1. If there is no such element, it must return -1. My code works, but needs to be optimized and run faster, below 1.5 seconds. Can anyone help? Follow the code below.

Grateful.

def index_equals_value(arr):
    hits = 0
    if len(arr)==1:
        return arr[0]
    for number in arr:
        if arr.index(number) == number:
            hits += 1
            hit_nmbr = number
            if hits > 1:
                return 1
                break
    if hits == 1:
        return hit_nmbr
   else:
       return -1

Answer 1

Your algorithm has an important bug. Documentation:

list.index(x[, start[, end]])

Return zero-based index in the list of the first item Whose value is Equal to x

This means that your algorithm only compares number with the first occurrence of that element in the list. I mean, he misses the next case, for example:

l = [2, 0, 2]

def index_equals_value(arr):
    hits = 0
    if len(arr)==1:
        return arr[0]
    for number in arr:
        if arr.index(number) == number:
            hits += 1
            hit_nmbr = number
            if hits > 1:
                return 1
    if hits == 1:
        return hit_nmbr
    else:
        return -1

print(index_equals_value(l))  # -1

Here the 2 in position 2 satisfies the desired condition, but the comparison always happens with index 0, because there is the first occurrence of number 2.

Incidentally, the index It’s also a very slow function because it checks the entire list until it finds the first element passed to it. I mean, if you’re looking for a number x and it occurs only in the 30000000 element of the list, the index will go through 30000000 elements before finding and returning, when in fact we just need to know if arr[x] == x.

---

Measuring time of execution:

# Criar lista aleatória
import random
l = [random.randint(0, 2000) for _ in range(2000)]

-

%%timeit
index_equals_value(l)  # Medir tempo de execução da função original
# 27.6 ms ± 2.54 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

-

def index_equals_value_2(arr):
    hits = 0
    if len(arr)==1:
        return arr[0]
    for number in arr:
        if arr[number] == number:
            hits += 1
            hit_nmbr = number
            if hits > 1:
                return 1
    if hits == 1:
        return hit_nmbr
    else:
        return -1

-

%%timeit
index_equals_value_2(l)  # Medir tempo de execução da função modificada
# 23.7 µs ± 108 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

---

As you can see, fixing the bug also accelerates the function by 3 orders of magnitude.

You should now treat the resulting exception of a if arr[number] == number if number is larger than the list size, or implement a check so that this check doesn’t happen. We also don’t want negative numbers to be counted backwards, so we have to ignore them:

def index_equals_value_2(arr):
    hits = 0
    if len(arr)==1:
        return arr[0]
    for number in arr:
        if number < 0 or number >= len(arr):
            continue  # Número não pode satisfazer condição
        if arr[number] == number:
            hits += 1
            hit_nmbr = number
            if hits > 1:
                return 1
    if hits == 1:
        return hit_nmbr
    else:
        return -1

At Anderson’s suggestion, we can also make a solution that iterates under the list with enumerate and directly compares the index to the value, and we don’t have to worry about that:

def index_equals_value_3(arr):
    hits = 0
    if len(arr)==1:
        return arr[0]
    for ind, number in enumerate(arr):
        if number == ind:
            hits += 1
            hit_nmbr = number
            if hits > 1:
                return 1
    if hits == 1:
        return hit_nmbr
    else:
        return -1

Answer 2

I tried the solution below for all cases raised by @Pedro von Hertwig and they worked instantly:

import random
random.seed(42)

def listSearch(x):
    ''' Procura o primeiro índice i tal que x[i]=i.
        Retorna -1 caso não encontre.'''
    for i in range(len(x)):
            if x[i]==i : return i
    return -1

# Caso 1: 
random.seed(2)
l = [random.randint(0, 2000) for _ in range(200000)]
l[199999]=199999
print('O índice é: ',listSearch(l)) # O índice é: 199999

# Caso 2: 
l = [0]
print('O índice é: ',listSearch(l)) # O índice é: 0

# Caso 3: 
l = [3]
print('O índice é: ',listSearch(l)) # O índice é: -1

# Caso 4: 
random.seed(42)
l = [random.randint(0, 20000000) for _ in range(200000)]
l[199999]=199999
print('O índice é: ',listSearch(l)) # O índice é: 873

# Caso 5: 
random.seed(2)
l = [random.randint(0, 2000) for _ in range(200000)]
l[0] = 199999
l[199999]=199999
print('O índice é: ',listSearch(l)) # O índice é: 199999

# Caso 6:
random.seed(2) 
l = [random.randint(0, 2000) for _ in range(200000)]
print('O índice é: ',listSearch(l)) # O índice é: -1