Algorithm complexity

If you comment parts of a ordered array , what you really need is to implement a binary search . In the case of cases you need O (log n) iterations, being OR (1) as regards memory use. In your current code the problem is in the line inter[p][1] where inter[p] is an integer, so you are trying to index on a scalar.

However, using a recursive algorithm is less readable, less efficient (more so if you make copies of the list with inter[j:] ) and you can end up exceeding the recursion limit.

An iterative approach I think is easier to understand and implement. The idea of the binary search is very simple, starting from a higher index and lower one among those you are looking for:

• If the lower index is greater than the higher one, the search ends without finding the value.

• We search for the index of the element by placing it in the middle, this being equal to (indice_superior + indice_inferior ) // 2 . Where // is the entire division.

• If the average element is less than the element sought, the lower index is equal to the index of the middle element plus 1.

• If the average element is greater than the one sought, the upper limit becomes the index of the average element minus 1.

• If the mean element is equal to the element sought, we return the element. Otherwise, we return to step two.

In this case we are not looking for the item, we look for the one that is immediately superior to it. The idea is nevertheless the same. A possible implementation would be:

def busqueda_binaria(inter, punto, inf=0, sup=None):

    # Si la lista está vacía retronamos None
    if not inter:
        return None

    # Si el índice superior es None se busca hasta el final de la lista
    if sup is None:
        sup = len(inter) - 1

    while inf < sup:
        medio = (sup + inf) // 2
        if inter[medio] <= punto:
            inf = medio + 1
        else:
            sup = medio

    return None if inter[inf] <= punto else inter[inf] 

If you want the index, just change the return by return None if inter[inf] <= punto else inf

Some tests:

>>> busqueda_binaria([10, 20, 21], 17)
20
>>> busqueda_binaria([10, 20, 21], 9)
10
>>> busqueda_binaria([10, 20, 21, 30], 17, inf=2)
21
>>> busqueda_binaria([2, 4, 8, 9, 10, 20, 21, 30, 32, 35], 8, inf=5, sup=8)
20
>>> busqueda_binaria([2, 4, 8, 9, 10, 20, 21, 30, 32, 35], 36, inf=5, sup=8)
>>> busqueda_binaria([], 4)

Both indexes are inclusive, if element is not found or the list has no elements, None is returned.

If we do a small test of a typical search iterating from the first element until we find the one we are looking for ( for elemento in lista: ) in front of the binary search we find a significant difference, especially in the worst case for the first approximation, the one in which you have to go through all the iterable because there is no greater element:

  

List length: 100000000 items.
    Binary: 0.014013051986694336 seconds.
    For: 14.315513372421265 seconds.

For this same example but for the best possible case for the simple iteration (the first element is already greater) and one of the worst for the binary search (the element is at the ends), the overload of the binary search it is proportionally insignificant, 27 iterations.

Edit:

If you require it to be recursive, the same logic can apply:

def terceraParte(lista, i, j, punto):
    if i >= j:
        if i < len(lista) and lista[i] > punto:
            return lista[i]
        return None

    else:
        p = (i+j)//2
        if lista[p] <= punto:
            return terceraParte(lista, p+1, j, punto)
        else:
            return terceraParte(lista, i, p , punto)

If you want the index change return lista[i] by return i simply.

The problem is here:

   if lista[i] >= punto:
        res = i

When it is met: lista[i] >= punto , you must actually match the value within the array not the index value ( i ), this to get the correct value:

    if lista[i] >= punto:
        res = lista[i] 

This would be the correct code:

lista = [1,5,10,15,20,25]

#Obtengo el indice del primer valor que es >= Punto
def segundaParte(lista,i,punto):
    if i == len(lista):
        res = - 1
    else:
        if lista[i] >= punto:
            res = lista[i] #***Correccion aqui!
        else:
            res = segundaParte(lista,i+1,punto)
    return res


print segundaParte(lista,0,12);