Búsqueda Binaria

Posted on

Hace 3 semanas, me dijeron a escribir una búsqueda binaria en JavaScript. Así que pensé que la escribiría para ustedes en Python.

Búsqueda Binaria

Una búsqueda binaria encuentra un elemento en una lista ordenada verificando si el elemento que está en el medio es mayor, menor, o igual que el elemento que se busca. Si es menor, la búsqueda binaria repite sólo el procidimiento en la parte superior ub. Si es mayor, la función se repita el procidimiento en la parte inferior lb. Si es igual, el elemento se ha encontrado. Una búsqueda binaria tiene en el peor de los casos O(log n).

def biSearch(lista, el):
    """Necesita ser una lista ordenada"""
    
    ub = len(lista) -1
    lb = 0

    while (lb < ub-1):
        med = (ub + lb) // 2

        if lista[med] == el:
            return True
        elif lista[med] < el:
            lb = med +1
        elif lista[med] > el:
            ub = med -1
    
    return False

Ustedes deben saber que una búsqueda binaria puede ser peor que una búsqueda lineal en el caso de una lista pequeña, porque el tiempo que toma ordenar la lista puede no valer la pena. O si la lista es grande y no ordenada, probablemente quieras considerar si la ordenación más la búsqueda binaria tardarían menos que la búsqueda lineal.

El Recursivo

def busquedaBinaria(unaLista, item):
    if len(unaLista) == 0:
        return False
    else:
        puntoMedio = len(unaLista)//2
        if unaLista[puntoMedio]==item:
            return True
        else:
            if item<unaLista[puntoMedio]:
                return busquedaBinaria(unaLista[:puntoMedio],item)
            else:
                return busquedaBinaria(unaLista[puntoMedio+1:],item)

Esto es de interactivepython.org. Yo era demasiado vago para escribir el mío. 

El algoritmo recursivo se usa más memoria que el algoritmo iterativo y el uso del operador de partición cambia el peor de los casos. En Python, el operador de partición es O(n).


Por más información:

http://interactivepython.org/runestone/static/pythoned/SortSearch/LaBusquedaBinaria.html

https://es.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search

Nota del Autor: Probablemente, yo escribiré un algoritmo recursivo más tarde hoy. interactivepython.org es un bueneo sitio web.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *