python

Algoritmo de búsqueda binaria en listas y arreglos de Python

Introducción

Continuamos con la serie de tutoriales acerca de la implementación del algoritmo de búsqueda binaria en muchos lenguajes de programación.

Hoy es el turno de un lenguaje que uso para automatizar cosas: Python. En Python los arreglos son conocidos como listas.

Veremos cómo implementar el algoritmo de búsqueda binaria tanto recursivamente como con un ciclo while; esto último también es llamado búsqueda binaria secuencial.

Realmente, cuando conocemos el algoritmo, su aplicación en un lenguaje de programación es sencillo. Pero bueno, vamos al punto. En resumen:

  • Veremos cómo implementar el algoritmo de búsqueda binaria en listas de Python, usando recursividad
  • Aplicaremos el algoritmo de búsqueda binaria en arreglos de Python (lo mismo que las listas), pero sin usar recursividad.

Lecturas recomendadas

He escrito este mismo algoritmo en otros lenguajes, puedes darles una revisión si quieres 🙂

Búsqueda binaria en JavaScript

PHP y el algoritmo de búsqueda binaria en arreglos

Sobre las cadenas y números

Python y JavaScript tratan a las cadenas lexicográficamente. Es decir, podemos compararlas como si de números se tratara, usando los operadores <, >, <= y >=, entre otros.

Esto permite que podamos usar el mismo algoritmo para buscar tanto en listas de números como de cadenas.

Sólo quería decir eso, ahora sí veamos cómo se implementa.

Búsqueda binaria en lista de Python usando recursividad

Primero veamos la forma que más me agrada, y es la búsqueda binaria pero usando recursividad o recursión. Aquí el código:

"""
    Algoritmo de búsqueda binaria recursiva escrito en Python
    Este método funciona con cadenas y números por igual, pues
    este lenguaje (justo como JavaScript) trata a las cadenas
    lexicográficamente; comparando sus valores en el código ASCII
 
    @author parzibyte
    @web parzibyte.me/blog
"""
def busqueda_binaria_recursiva(arreglo, busqueda, izquierda, derecha):
    if izquierda > derecha:
        return -1
    indiceDelElementoDelMedio = (izquierda + derecha) // 2
    elementoDelMedio = arreglo[indiceDelElementoDelMedio]
    if elementoDelMedio == busqueda:
        return indiceDelElementoDelMedio
    if busqueda < elementoDelMedio:
        return busqueda_binaria_recursiva(arreglo, busqueda, izquierda, indiceDelElementoDelMedio - 1)
    else:
        return busqueda_binaria_recursiva(arreglo, busqueda, indiceDelElementoDelMedio + 1, derecha)

Primero lo llamamos con izquierda en 0 y derecha con la longitud del arreglo – 1. Luego vemos su elemento del medio y si es ese el que buscamos, regresamos el índice.

Si no es el elemento, adivinamos si lo que buscamos está hacia la izquierda o hacia la derecha, y partimos el arreglo justamente ahí.

Quiero recalcar que no usamos floor o una función explícita, pues con el operador // se redondea hacia abajo (una de las pocas cosas que me gustan de Python)

Todo está encerrado en una función para fomentar la reutilización. Veamos cómo se usa.

Búsqueda binaria en arreglos de números

Si tenemos un arreglo numérico, podemos hacer esto:

"""
Probar con arreglo numérico
"""
arreglo = [1, 2, 3, 10, 50, 80, 120, 150, 500, 1000]
print("Vamos a buscar en la siguiente lista:", arreglo)
busqueda = 500
indice = busqueda_binaria_recursiva(arreglo, busqueda, 0, len(arreglo) - 1)
print("El elemento {} está en el índice {}".format(busqueda, indice))

La salida es:

Vamos a buscar en la siguiente lista: [1, 2, 3, 10, 50, 80, 120, 150, 500, 1000]
El elemento 500 está en el índice 8

Está de más decir que si no encuentra el valor regresa -1.

Búsqueda binaria en lista de strings

Para un arreglo de cadenas es lo mismo, aquí el código:

"""
Probar con arreglo de cadenas
"""
arreglo = ["Albino", "Bambú", "Becerro", "Contaminación", "Cortina", "Trampolín"]
print("La otra lista es:", arreglo)
busqueda = "Cortina"
indice = busqueda_binaria_recursiva(arreglo, busqueda, 0, len(arreglo) - 1)
print("El elemento {} está en el índice {}".format(busqueda, indice))

La salida en este caso es:

La otra lista es: [‘Albino’, ‘Bambú’, ‘Becerro’, ‘Contaminación’, ‘Cortina’, ‘Trampolín’]
El elemento Cortina está en el índice 4

El algoritmo no cambia, simplemente cambian los tipos de datos. Ahora veamos cómo hacer esto pero con while; me ahorraré la explicación porque es lo mismo pero sin usar recursión o recursividad.

Algoritmo de búsqueda binaria en lista de Python usando un ciclo

Veamos ahora cómo se hace con un ciclo.

Como decía al principio, esto también es llamado búsqueda binaria secuencial.

Básicamente cambiamos los valores de izquierda y derecha dentro del ciclo, es decir, vamos partiendo la lista en el interior del ciclo while.

Si el ciclo se termina (cuando izquierda es mayor que derecha) entonces regresamos -1.

"""
    Algoritmo de búsqueda binaria usando el ciclo while
    escrito en Python.
 
    Este método funciona con cadenas y números por igual, pues
    este lenguaje (justo como JavaScript) trata a las cadenas
    lexicográficamente; comparando sus valores en el código ASCII
 
    @author parzibyte
    @web parzibyte.me/blog
"""
def busqueda_binaria(arreglo, busqueda):
    izquierda, derecha = 0, len(arreglo) - 1
    while izquierda <= derecha:
        indiceDelElementoDelMedio = (izquierda + derecha) // 2
        elementoDelMedio = arreglo[indiceDelElementoDelMedio]
        if elementoDelMedio == busqueda:
            return indiceDelElementoDelMedio
        if busqueda < elementoDelMedio:
            derecha = indiceDelElementoDelMedio - 1
        else:
            izquierda = indiceDelElementoDelMedio + 1
    # Si salimos del ciclo significa que no existe el valor
    return -1

Probar función

Para probar la función que acabamos de crear podemos implementar el siguiente código, el cual prueba arreglos numéricos y de cadenas:

"""
Probar con arreglo numérico
"""
arreglo = [1, 2, 3, 10, 50, 80, 120, 150, 500, 1000]
print("Vamos a buscar en la siguiente lista:", arreglo)
busqueda = 500
indice = busqueda_binaria(arreglo, busqueda)
print("El elemento {} está en el índice {}".format(busqueda, indice))
 
 
"""
Probar con arreglo de cadenas
"""
arreglo = ["Albino", "Amanda", "Bambú", "Becerro", "Contaminación", "Cortina", "Trampolín"]
print("La otra lista es:", arreglo)
busqueda = "Cortina"
indice = busqueda_binaria(arreglo, busqueda)
print("El elemento {} está en el índice {}".format(busqueda, indice))

La salida es:

Vamos a buscar en la siguiente lista: [1, 2, 3, 10, 50, 80, 120, 150, 500, 1000]
El elemento 500 está en el índice 8
La otra lista es: [‘Albino’, ‘Amanda’, ‘Bambú’, ‘Becerro’, ‘Contaminación’, ‘Cortina’, ‘Trampolín’]
El elemento Cortina está en el índice 5

Y así de fácil es implementar este algoritmo en Python.

Estoy aquí para ayudarte 🤝💻


Estoy aquí para ayudarte en todo lo que necesites. Si requieres alguna modificación en lo presentado en este post, deseas asistencia con tu tarea, proyecto o precisas desarrollar un software a medida, no dudes en contactarme. Estoy comprometido a brindarte el apoyo necesario para que logres tus objetivos. Mi correo es parzibyte(arroba)gmail.com, estoy como@parzibyte en Telegram o en mi página de contacto

No te pierdas ninguno de mis posts 🚀🔔

Suscríbete a mi canal de Telegram para recibir una notificación cuando escriba un nuevo tutorial de programación.
parzibyte

Programador freelancer listo para trabajar contigo. Aplicaciones web, móviles y de escritorio. PHP, Java, Go, Python, JavaScript, Kotlin y más :) https://parzibyte.me/blog/software-creado-por-parzibyte/

Ver comentarios

Entradas recientes

Creador de credenciales web – Aplicación gratuita

Hoy te voy a presentar un creador de credenciales que acabo de programar y que…

12 horas hace

Desplegar PWA creada con Vue 3, Vite y SQLite3 en Apache

Ya te enseñé cómo convertir una aplicación web de Vue 3 en una PWA. Al…

7 días hace

Arquitectura para wasm con Go, Vue 3, Pinia y Vite

En este artículo voy a documentar la arquitectura que yo utilizo al trabajar con WebAssembly…

7 días hace

Vue 3 y Vite: crear PWA (Progressive Web App)

En un artículo anterior te enseñé a crear un PWA. Al final, cualquier aplicación que…

7 días hace

Errores de Comlink y algunas soluciones

Al usar Comlink para trabajar con los workers usando JavaScript me han aparecido algunos errores…

7 días hace

Esperar promesa para inicializar Store de Pinia con Vue 3

En este artículo te voy a enseñar cómo usar un "top level await" esperando a…

7 días hace

Esta web usa cookies.