Bienvenidos
En este artículo, aprenderá cómo funciona el algoritmo de búsqueda binaria entre bastidores y cómo puede implementarlo en Python.
En particular, aprenderá:
- Cómo funciona el algoritmo detrás de escena para encontrar un elemento objetivo.
- Cómo funciona su implementación de Python línea por línea.
- Por qué es un algoritmo muy eficiente en comparación con la búsqueda lineal.
- Sus ventajas y requisitos.
¡Vamos a empezar! ✨
? Introducción a la búsqueda binaria
Este algoritmo se utiliza para encontrar un elemento en una secuencia ordenada (por ejemplo: una lista, tupla o cadena).
Requisitos
Para aplicar el algoritmo de búsqueda binaria a una secuencia, la secuencia ya debe estar ordenada en orden ascendente. De lo contrario, el algoritmo no encontrará la respuesta correcta. Si lo hace, será por pura coincidencia.
? Sugerencia: puede ordenar la secuencia antes de aplicar la búsqueda binaria con un algoritmo de ordenación que satisfaga sus necesidades.
Entrada y salida
El algoritmo (implementado como una función) necesita estos datos:
- Una secuencia ordenada de elementos (por ejemplo: lista, tupla, cadena).
- El elemento de destino que estamos buscando.
Devuelve el índice del elemento que está buscando si se encuentra. Si no se encuentra el elemento, se devuelve -1.
Eficiencia
Es muy eficiente en comparación con la búsqueda lineal (buscar un elemento uno por uno, comenzando desde el primero) porque podemos "descartar" la mitad de la lista en cada paso.
Empecemos a sumergirnos en este algoritmo.
? Tutorial visual
Aplicaremos el algoritmo de búsqueda binaria a esta lista:
? Sugerencia: observe que la lista ya está ordenada. Incluía los índices como referencia visual.
Objetivo
Queremos encontrar el índice del entero 67 .
Intervalo
Supongamos que somos el algoritmo. ¿Cómo iniciamos el proceso?
Empezamos seleccionando los dos límites del intervalo donde queremos buscar. Queremos buscar en toda la lista, por lo que seleccionamos índice 0como límite inferior e índice 5como límite superior:
Elemento medio
Ahora necesitamos encontrar el índice del elemento medio en este intervalo. Hacemos esto sumando el límite inferior y el límite superior y dividiendo el resultado por 2 usando la división de enteros.
En este caso, (0 + 5)//2se 2debe a que el resultado de 5/2es 2.5y la división entera trunca la parte decimal.
Entonces, el elemento del medio está ubicado en el índice 2 , y el elemento del medio es el número 6 :
Comparaciones
Ahora debemos comenzar a comparar el elemento intermedio con nuestro elemento objetivo para ver qué debemos hacer a continuación.
Le pedimos:
¿El elemento del medio es igual al elemento que estamos buscando?
6 == 67 # FalseNo, no lo es.
Entonces preguntamos:
¿El elemento del medio es mayor que el elemento que buscamos?
6 > 67 # FalseNo, no lo es.
Entonces, el elemento del medio es más pequeño que el elemento que estamos buscando.
6 < 67 # TrueDescartar elementos
Dado que la lista ya está ordenada, esto nos dice algo extremadamente importante. Nos dice que podemos "descartar" la mitad inferior de la lista porque sabemos que todos los elementos que vienen antes del elemento del medio serán más pequeños que el elemento que estamos buscando, por lo que nuestro elemento de destino no está allí.
Empezar de nuevo: elegir los límites
¿Qué hacemos a continuación? Hemos descartado los elementos y el ciclo se repite nuevamente.
Tenemos que elegir los límites para el nuevo intervalo (ver más abajo). Pero observe que el límite superior se mantiene intacto y solo se cambia el límite inferior.
Esto se debe a que el elemento que estamos buscando podría estar en la mitad superior de la lista. El límite superior se mantiene intacto y el límite inferior se cambia para "reducir" el intervalo a un intervalo en el que podría encontrarse nuestro elemento de destino.
? Sugerencia: Si el elemento del medio hubiera sido mayor que el elemento que buscamos, el límite superior se habría cambiado y el límite inferior se habría mantenido intacto. De esta manera, descartaríamos la mitad superior de la lista y seguiríamos buscando en la mitad inferior.
Elemento medio
Ahora necesitamos encontrar el índice del elemento del medio agregando el límite inferior al límite superior y dividiendo el resultado por 2 usando la división entera.
El resultado de (3+5)//2es 4, por lo que el elemento del medio está ubicado en el índice4 y el elemento del medio es 67 .
Comparaciones
Le pedimos:
¿El elemento del medio es igual al elemento que estamos buscando?
67 == 67 # True¡Sí lo es! Entonces hemos encontrado el elemento en el índice 4 . Se devuelve el valor 4 y el algoritmo se completó correctamente.
? Sugerencia: Si no se hubiera encontrado el elemento, el proceso habría continuado hasta que el intervalo ya no fuera válido. Si el elemento no se hubiera encontrado en toda la lista, se habría devuelto -1.
? Tutorial de código
Ahora que tiene una intuición visual de cómo funciona el algoritmo detrás de escena, profundicemos en la implementación iterativa de Python analizándola línea por línea:
def binary_search(data, elem): low = 0 high = len(data) - 1 while low elem: high = middle - 1 else: low = middle + 1 return -1Encabezamiento
Aquí tenemos el encabezado de la función:
def binary_search(data, elem):Se necesitan dos argumentos:
- La secuencia ordenada de elementos (por ejemplo: lista, tupla o cadena).
- El elemento que queremos encontrar.
Intervalo inicial
La siguiente línea establece los límites inicial inferior y superior:
low = 0 high = len(data) - 1El límite inferior inicial es el índice 0y el límite superior inicial es el último índice de la secuencia.
Lazo
Repetiremos el proceso mientras haya un intervalo válido, mientras que el límite inferior sea menor o igual que el límite superior.
while low <= high:? Consejo: recuerde que los límites son índices.
Elemento medio
En cada iteración, necesitamos encontrar el índice del elemento del medio. Para hacer esto, sumamos los límites inferior y superior y dividimos el resultado por 2 usando la división de enteros.
middle = (low + high)//2? Consejo: utilizamos la división de enteros en caso de que la lista o el intervalo contenga un número par de elementos. Por ejemplo, si la lista tuviera 6 elementos y no usáramos división entera, middlesería el resultado de (0 + 5)/2cuál es 2.5. Un índice no puede ser un flotante, por lo que truncamos la parte decimal usando //y seleccionamos el elemento en el índice 2.
Comparaciones
Con estos condicionales (ver más abajo), determinamos qué hacer dependiendo del valor del elemento intermedio data[middle]. Lo comparamos con el elemento objetivo que estamos buscando.
if data[middle] == elem: return middle elif data[middle] > elem: high = middle - 1 else: low = middle + 1Hay tres opciones:
- Si el elemento del medio es igual al elemento que estamos buscando, devolvemos el índice inmediatamente porque encontramos el elemento.
if data[middle] == elem: return middle- Si el elemento del medio es mayor que el elemento que estamos buscando, reasignamos el límite superior porque sabemos que el elemento de destino está en la mitad inferior de la lista.
elif data[middle] > elem: high = middle - 1- De lo contrario, la única opción que queda es que el elemento del medio es más pequeño que el elemento que estamos buscando, por lo que reasignamos el límite inferior porque sabemos que el elemento de destino está en la mitad superior de la lista.
else: low = middle + 1Elemento no encontrado
Si el ciclo se completa sin encontrar el elemento, se devuelve el valor -1.
return -1y tenemos la implementación final del algoritmo de búsqueda binaria:
def binary_search(data, elem): low = 0 high = len(data) - 1 while low elem: high = middle - 1 else: low = middle + 1 return -1? Casos especiales
Estos son algunos casos particulares que puede encontrar al comenzar a trabajar con este algoritmo:
Elementos repetidos
Si el elemento que está buscando se repite en la secuencia, el índice devuelto dependerá del número de elementos y de la secuencia de operaciones que el algoritmo realice en la secuencia.
>>> >>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 7) 4 Elemento no encontrado
Si no se encuentra el elemento, se devuelve -1.
>>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 8) -1Secuencia vacía
Si la secuencia está vacía, se devolverá -1.
>>> b = [] >>> binary_search(b, 8) -1Secuencia sin clasificar
Si la secuencia no está ordenada, la respuesta no será correcta. Obtener el índice correcto es pura coincidencia y podría deberse al orden de los elementos en la secuencia y la secuencia de operaciones realizadas por el algoritmo.
Este ejemplo devuelve el resultado correcto:
>>> b = [5, 7, 3, 0, -9, 2, 6] >>> binary_search(b, 6) 6Pero este no:
>>> b = [5, 7, 3, 0, -9, 2, 10, 6] >>> binary_search(b, 6) -1? Consejo: Piense por qué el primer ejemplo devuelve el resultado correcto. Sugerencia: es pura coincidencia que el orden de los elementos haga que el algoritmo alcance el índice correcto, pero el proceso paso a paso evalúa 0, luego 2y finalmente 6. En este caso particular, para este elemento en particular, se encuentra el índice correcto incluso si la secuencia no está ordenada.
? Un ejemplo más complejo
Ahora que está más familiarizado con el algoritmo y su implementación de Python, aquí tenemos un ejemplo más complejo:
Queremos encontrar el índice del elemento 45 en esta lista usando la búsqueda binaria:
Primera iteración
Se seleccionan los límites inferior y superior:
Se selecciona el elemento intermedio ( 26 ):
Pero el elemento del medio ( 26 ) no es el elemento que buscamos, es menor que 45 :
Segunda iteración
Entonces podemos descartar todos los elementos que son más pequeños que el elemento del medio y seleccionar nuevos límites. El nuevo límite inferior ( 27 ) es el elemento ubicado inmediatamente a la derecha del elemento intermedio anterior:
? Consejo: recuerde que la lista ya está ordenada.
Se selecciona el nuevo elemento intermedio ( 30 ):
El elemento del medio ( 30 ) no es el elemento que buscamos, es menor que 45 :
Tercera iteración
Podemos descartar los elementos que sean menores o iguales a 30 que aún no se hayan descartado. El límite inferior se actualiza a 32 :
Aquí tenemos un caso interesante: el elemento del medio es uno de los límites del intervalo actual porque (7+8)//2es 7.
El elemento del medio ( 32 ) no es el elemento que buscamos ( 45 ), es más pequeño.
Cuarta iteración
Podemos descartar los elementos que sean menores o iguales a 32 que no se hayan descartado ya.
Aquí tenemos otro caso muy interesante: el intervalo solo tiene un elemento.
? Sugerencia: Este intervalo es válido porque escribimos esta condición while high <= low:, que incluye intervalos donde el índice del límite inferior es igual al índice del límite superior.
El elemento del medio es el único elemento en el intervalo porque (8+8)//2es 8, por lo que el índice del elemento del medio es 8 y el elemento del medio es 45 .
Ahora el elemento del medio es el elemento que estamos buscando, 45 :
Entonces se devuelve el valor 8 (el índice):
>>> binary_search([1, 3, 7, 15, 26, 27, 30, 32, 45], 45) 8? Práctica adicional
Si desea practicar más con este algoritmo, intente explicar cómo funciona el algoritmo entre bastidores cuando se aplica a esta lista para encontrar el entero 90 :
[5, 8, 15, 26, 38, 56]- ¿Qué pasa paso a paso?
- ¿Qué valor se devuelve?
- ¿Se encuentra el elemento?
Realmente espero que les haya gustado mi artículo y les haya resultado útil. Ahora puede implementar el algoritmo de búsqueda binaria en Python. Consulte mi curso en línea "Algoritmos de búsqueda y clasificación de Python: un enfoque práctico". Sigueme en Twitter. ⭐️