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:
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
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.
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:
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.
Si tenemos un arreglo numérico, podemos hacer esto:
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.
Para un arreglo de cadenas es lo mismo, aquí el código:
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.
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.
Para probar la función que acabamos de crear podemos implementar el siguiente código, el cual prueba arreglos numéricos y de cadenas:
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.
La impresión de un PDF en cualquier impresora se puede automatizar con un bot de…
Hoy te enseñaré cómo enviar un mensaje a un usuario desde un bot de Telegram…
El día de hoy te enseñaré algo muy sencillo pero útil al programar con PHP:…
El plugin para imprimir en impresoras térmicas alcanza hoy su versión 3.4.0 agregando soporte para…
En ocasiones es necesario leer los pixeles y colores de una imagen con JavaScript del…
Siguiendo con los tutoriales de listas desplegables o select con JavaScript, vamos a ver cómo…
Esta web usa cookies.
Ver comentarios