| Author: Eduardo Enriquez

Python: binary search algorithm (b煤squeda binaria)

La聽b煤squeda binaria es un聽algoritmo de b煤squeda聽que encuentra la posici贸n de un valor en un聽array ordenado. Lo que hace el algoritmo es empezar a comparar valores desde la mitad de mi lista o array. En el caso de que sea mayor el numero buscado, el algoritmo seguira buscando a partir de la mitad restante de la derecha y tambi茅n a partir de la mitad.聽

La b煤squeda binaria tiene聽en el peor de los casos聽un tiempo logar铆tmico, realizando O(log n)聽comparaciones, donde n es el n煤mero de elementos del array and log es el聽logaritmo. La b煤squeda binaria requiere solamente O(1) en espacio, es decir, que el espacio requerido por el algoritmo es el mismo para cualquier cantidad de elementos en el array.

def binary_search(number, aList):
    left = 0
    right = len(aList)
    found = False

    while left < right:
        mid = (left + right) / 2
        if aList[mid] < number:
            left = mid + 1
        else:
            right = mid

    if number == aList[left]:
        found = True
        position = left

        return found, position

    return found

M谩s info en wikipedia聽y algo en toptal

Related Posts