Búsqueda binaria

La búsqueda binaria encuentra la posición de un elemento en una lista ordenada, comparando el elemento con el valor de al medio de la lista, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continúa en la mitad restante hasta que el valor se encuentre.

Por ejemplo, se desea encontrar el \(10\) en la siguiente lista:

4

6

10

12

17

25

29

Comparar el elemento buscado con el valor central: \(10 < 12\), es menor, entonces descartar el lado derecho.

4

6

10

Comparar el elemento buscado con el valor central: \(10 > 6\), es mayor, entonces descartar el lado izquierdo.

6

Comparar el elemento buscado con el valor central: \(10 = 10\), es igual, entonces se encontró.

Si hubiesen sido distintos, como no quedan más elementos, el valor buscado no está en la lista.

Escriba la función busqueda_binaria(lista, elemento)que recibe una lista ordenada y un elemento que se desea encontrar. La función debe retornar True si encuentra el elemento en la lista utilizando una búsqueda binaria. Si no se encuentra retornar False.

Ejemplos

>>> búsqueda_binaria([0, 1, 3, 8, 14, 18, 19, 34, 52], 3)
True
>>> búsqueda_binaria([0, 1, 3, 8, 14, 18, 19, 34, 52], 17)
False

Solución

def busqueda_binaria(lista, elemento):
    i = 0 # Indice izquierdo de la lista
    d = len(lista) - 1 # Indice derecho de la lista
    while i <= d: # Buscamos mientras no se crucen los indices
        m = (d + i) // 2 # Punto medio
        if lista[m] == elemento: # Si encuentra el elemento
            return True # Retorna verdadero
        elif lista[m] > elemento: # Si el valor del elemento es menor 
            # Nos quedamos con la parte izquierda del arreglo, es decir, el indice derecho es el punto medio - 1
            d = m - 1  
        elif lista[m] < elemento: # Si el valor del elemento es mayor
            # Nos quedamos con la parte derecha del arreglo, es decir, el indice izquierdo es el punto medio + 1
            i = m + 1
    return False # No encontramos el elemento
# Pruebas
print(busqueda_binaria([0, 1, 3, 8, 14, 18, 19, 34, 52], 3))
print(busqueda_binaria([0, 1, 3, 8, 14, 18, 19, 34, 52], 17))