Introducción
En este artículo, profundizaremos en la idea y la implementación de Python de Búsqueda binaria.
Binary Search es un algoritmo de búsqueda eficiente que funciona en matrices ordenadas. A menudo se usa como uno de los primeros ejemplos de algoritmos que se ejecutan en tiempo logarítmico (O (logn)) debido a su comportamiento intuitivo, y es un algoritmo fundamental en informática.
Búsqueda binaria - Ejemplo
Binary Search funciona en un enfoque de divide y vencerás y se basa en el hecho de que la matriz se ordena para eliminar la mitad de los posibles candidatos en cada iteración. Más específicamente, compara el elemento central de la matriz ordenada con el elemento que está buscando para decidir dónde continuar la búsqueda.
Si el elemento de destino es más grande que el elemento del medio, no se puede ubicar en la primera mitad de la colección, por lo que se descarta. Lo mismo ocurre al revés.
Nota: Si la matriz tiene un número par de elementos, no importa cuál de los dos elementos "intermedios" usamos para empezar.
Veamos un ejemplo rápidamente antes de continuar explicando cómo funciona la búsqueda binaria:
Como podemos ver, sabemos con certeza que, dado que la matriz está ordenada, x no está en la primera mitad de la matriz original.
Cuando sabemos en qué mitad de la matriz original x es decir, podemos repetir este proceso exacto con esa mitad y dividirlo en mitades nuevamente, descartando la mitad que seguramente no contiene x:
Repetimos este proceso hasta que terminemos con una submatriz que contenga solo un elemento. Verificamos si ese elemento es x. Si es así, encontramos xsi no lo es x no existe en la matriz en absoluto.
Si observa esto más de cerca, puede notar que en el peor de los casos (x no existe en la matriz), necesitamos verificar un número mucho menor de elementos de los que necesitaríamos en una matriz sin clasificar, lo que requeriría algo más en la línea de Búsqueda lineal, que es increíblemente ineficiente.
Para ser más precisos, la cantidad de elementos que debemos verificar en el peor de los casos es log2N donde N es el número de elementos en la matriz.
Esto tiene un impacto mayor cuanto más grande es la matriz:
Si nuestra matriz tuviera 10 elementos, necesitaríamos verificar solo 3 elementos para encontrar x o concluir que no está allí. Eso es 33.3%.
Sin embargo, si nuestra matriz tuviera 10,000,000 elementos, solo necesitaríamos verificar 24 elementos. Eso es 0.0002%.
Implementación de búsqueda binaria
Binary Search es un algoritmo naturalmente recursivo, ya que el mismo proceso se repite en matrices cada vez más pequeñas hasta que se encuentre una matriz de tamaño 1. Sin embargo, por supuesto, también hay una implementación iterativa, y mostraremos ambos enfoques.
recursiva
Comencemos con la implementación recursiva, ya que es más natural:
def binary_search_recursive(array, element, start, end): if start > end: return -1 mid = (start + end) // 2 if element == array[mid]: return mid if element < array[mid]: return binary_search_recursive(array, element, start, mid-1) else: return binary_search_recursive(array, element, mid+1, end)
Echemos un vistazo más de cerca a este código. Salimos de la recursividad si el start elemento es más alto que el end elemento:
if start > end: return -1
Esto se debe a que esta situación ocurre solo cuando el elemento no existe en la matriz. Lo que sucede es que terminamos con solo un elemento en la sub-matriz actual, y ese elemento no coincide con el que estamos buscando.
En este punto, start es igual a end. Sin embargo, desde element no es igual a array[mid], "dividimos" la matriz nuevamente de tal manera que disminuimos end en 1, o aumentar start por uno, y la recursión existe en esa condición.
Podríamos haber hecho esto usando un enfoque diferente:
if len(array) == 1: if element == array[mid]: return mid else: return -1
El resto del código hace la lógica de "verificar elemento intermedio, continuar buscando en la mitad apropiada de la matriz". Encontramos el índice del elemento del medio y verificamos si el elemento que estamos buscando coincide:
mid = (start + end) // 2
if elem == array[mid]: return mid
Si no es así, verificamos si el elemento es más pequeño o más grande que el elemento del medio:
if element < array[mid]: # Continue the search in the left half return binary_search_recursive(array, element, start, mid-1)
else: # Continue the search in the right half return binary_search_recursive(array, element, mid+1, end)
Avancemos y ejecutemos este algoritmo, con una ligera modificación para que imprima en qué subarray está trabajando actualmente:
element = 18
array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29] print("Searching for {}".format(element))
print("Index of {}: {}".format(element, binary_search_recursive(array, element, 0, len(array))))
Ejecutar este código dará como resultado:
Searching for 18
Subarray in step 0:[1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 1:[16, 18, 24, 28, 29]
Subarray in step 2:[16, 18]
Subarray in step 3:[18]
Index of 18: 7
Está claro ver cómo reduce a la mitad el espacio de búsqueda en cada iteración, acercándose cada vez más al elemento que estamos buscando. Si intentamos buscar un elemento que no existe en la matriz, el resultado sería:
Searching for 20
Subarray in step 0: [4, 14, 16, 17, 19, 21, 24, 28, 30, 35, 36, 38, 39, 40, 41, 43]
Subarray in step 1: [4, 14, 16, 17, 19, 21, 24, 28]
Subarray in step 2: [19, 21, 24, 28]
Subarray in step 3: [19]
Index of 20: -1
Y solo por el gusto de hacerlo, podemos intentar buscar algunos arreglos grandes y ver cuántos pasos se necesitan para la Búsqueda binaria para determinar si existe un número:
Searching for 421, in an array with 200 elements
Search finished in 6 steps. Index of 421: 169 Searching for 1800, in an array with 1500 elements
Search finished in 11 steps. Index of 1800: -1 Searching for 3101, in an array with 3000 elements
Search finished in 8 steps. Index of 3101: 1551
Iterativo
El enfoque iterativo es muy simple y similar al enfoque recursivo. Aquí, solo realizamos las comprobaciones en un while bucle:
def binary_search_iterative(array, element): mid = 0 start = 0 end = len(array) step = 0 while (start <= end): print("Subarray in step {}: {}".format(step, str(array[start:end+1]))) step = step+1 mid = (start + end) // 2 if element == array[mid]: return mid if element < array[mid]: end = mid - 1 else: start = mid + 1 return -1
Llenemos una matriz y busquemos un elemento dentro de ella:
array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29] print("Searching for {} in {}".format(element, array))
print("Index of {}: {}".format(element, binary_search_iterative(array, element)))
Ejecutar este código nos da la salida de:
Searching for 18 in [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 0: [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 1: [16, 18, 24, 28, 29]
Subarray in step 2: [16, 18]
Subarray in step 3: [18]
Index of 18: 7
Conclusión
La búsqueda binaria es un algoritmo increíble para usar en matrices grandes y ordenadas, o siempre que planeemos buscar elementos repetidamente en una sola matriz.
El costo de ordenar la matriz una vez y luego usar la Búsqueda binaria para encontrar elementos en ella varias veces es mucho mejor que usar la Búsqueda lineal en una matriz no ordenada solo para que podamos evitar el costo de ordenarla.
Si estamos ordenando la matriz y buscando un elemento solo una vez, es más eficiente hacer una búsqueda lineal en la matriz no ordenada.
Si desea leer sobre Algoritmos de clasificación en Python, ¡te tenemos cubierto!
