Python: binary search algorithm (búsqueda binaria)

25/12/2017 | Autor: Eduardo Enriquez

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


Tags