CODEWITHSUNDEEP
pythonarraysvectorindexing
Lucas Vázquez
Lucas Vázquez

Reputation: 1

Is there any way to find if the index is equal to the element of a vector?

Using the methodology of Divide and Conquer, I'm trying to do an algorithm that compares if the index of a vector is equal to the element in this position. I've seen that my code is inefficient in large vectors, so I've been thinking to do it by dividing the vector in two halves, but I do not know how to do it...

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))

I introduce the number of elements in the vector: 7 Introduce the elements separate by spaces: -3 -1 2 5 6 7 9 And the output should be 2 where the element is equal to the position

Upvotes: 0

Views: 1017

Answers (2)

DeepSpace
DeepSpace

Reputation: 81684

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

If the input array is not sorted, then the most efficient code will have a time complexity of O(n) since we have to iterate element by element and compare the index to the value. In this case, using divide and conquer is meaningless and is only adding complexity.

If the input array is sorted, then you can use a modified version of binary search to achieve an O(logn) time complexity.

Upvotes: 0

Samuel Nde
Samuel Nde

Reputation: 2753

How about just getting the list of indices where the index is equal to the 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.

Upvotes: 1

Related Questions