有没有办法找出索引是否等于向量的元素？

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

"I've seen that my code is inefficient in large vector"

如果输入数组没有排序，那么最有效的代码的时间复杂度将为O（n），因为我们必须逐个元素迭代并将索引与值进行比较。在这种情况下，使用分而治之是毫无意义的，只会增加复杂性。你知道吗

如果对输入数组进行排序，则可以使用二进制搜索的修改版本来实现O（logn）时间复杂度。你知道吗

Answer 2

我们来看看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.