Есть ли способ узнать, равен ли индекс элементу вектора?

Question

Используя методологию «Разделяй и властвуй», я пытаюсь создать алгоритм, который сравнивает, равен ли индекс вектора элементу в этой позиции.Я видел, что мой код неэффективен в больших векторах, поэтому я думал сделать это, разделив вектор на две половины, но я не знаю, как это сделать ...

def indicePosicion (inicio, lista):   
    if lista == []:
        return -1
    elif int(lista[0]) == inicio:
        return inicio
    else:
        return indicePosicion(inicio+1, lista[1:])

numero = int(input())
lista = input().split()
print(indicePosicion(0, lista))

Я ввел количество элементов в векторе: 7 Введите элементы, разделенные пробелами: -3 -1 2 5 6 7 9 И на выходе должно быть 2, где элемент равен позиции

Answer 1

Как насчет просто получить список индексов, где index равен element?

a = [1, 2, 3, 3, 4, 4, 6, 6]
[index for index, element in enumerate(a) if index == element] 
#gives you a list of indices of `a` with a value equal to the index.

Answer 2

"Я видел, что мой код неэффективен в большом векторе"

Если входной массив не отсортирован , то наиболее эффективный код будет иметь временную сложность O (n), так как мы должны повторять элемент за элементом и сравнивать индекс со значением. В этом случае использование «разделяй и властвуй» не имеет смысла и только добавляет сложности.

Если входной массив отсортирован , то вы можете использовать модифицированную версию двоичного поиска для достижения сложности времени O (logn).