Búsqueda binaria en Python

En este tutorial, cubriremos la búsqueda binaria en Python, su idea y la implementación iterativa y recursiva.

Introducción

En este artículo, nos sumergiremos en la idea detrás 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 Ciencias de la Computación.

Búsqueda binaria: ejemplo

Binary Search funciona con 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 "del medio" usemos para comenzar.

Veamos un ejemplo rápidamente antes de continuar explicando cómo funciona la búsqueda binaria:

búsqueda binaria en visualización python

Como podemos ver, sabemos con seguridad que, dado que la matriz está ordenada, x no está en la primera mitad de la matriz original.

Cuando sabemos en qué mitad del arreglo original está x, podemos repetir este mismo proceso con esa mitad y dividirla en mitades nuevamente, descartando la mitad que seguramente no contiene x:

búsqueda binaria en visualización python

Repetimos este proceso hasta que terminamos con un subarreglo que contiene solo un elemento. Comprobamos si ese elemento es x. Si lo es, encontramos x, si no lo es, x no existe en absoluto en la matriz.

Si observa esto más de cerca, puede notar que en el peor de los casos (x no existe en la matriz), necesitamos verificar una cantidad mucho menor de elementos de los que necesitaríamos en un desordenado matriz, 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 necesitamos verificar en el peor de los casos es log~2~N donde N es la cantidad de elementos en la matriz.

Esto tiene un mayor impacto 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

La búsqueda binaria es un algoritmo naturalmente recursivo, ya que el mismo proceso se repite en matrices cada vez más pequeñas hasta que se encuentra una matriz de tamaño 1. Sin embargo, por supuesto, también hay una implementación iterativa, y mostraremos ambos enfoques.

Recursivo

Comencemos con la implementación recursiva ya que es más natural:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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 elemento start es mayor que el elemento end:

1
2
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 un solo elemento en el subconjunto actual y ese elemento no coincide con el que estamos buscando.

En este punto, start es igual a end. Sin embargo, dado que element no es igual a array[mid], "dividimos" la matriz nuevamente de tal manera que reducimos end en 1, o aumentamos start en uno, y la recursión existe en esa condición.

Podríamos haber hecho esto usando un enfoque diferente:

1
2
3
4
5
if len(array) == 1:
    if element == array[mid]:
        return mid
    else:
        return -1

El resto del código hace la lógica "comprobar el elemento central, continuar buscando en la mitad apropiada de la matriz". Encontramos el índice del elemento central y verificamos si el elemento que estamos buscando coincide con él:

1
2
3
mid = (start + end) // 2
if elem == array[mid]:
    return mid

Si no es así, comprobamos si el elemento es más pequeño o más grande que el elemento del medio:

1
2
3
4
5
6
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é subarreglo está trabajando actualmente:

1
2
3
4
5
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:

1
2
3
4
5
6
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

Se ve claramente como reduce a la mitad el espacio de búsqueda en cada iteración, acercándose cada vez más al elemento que buscamos. Si intentamos buscar un elemento que no existe en la matriz, el resultado sería:

1
2
3
4
5
6
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 en matrices grandes y ver cuántos pasos requiere la búsqueda binaria para averiguar si existe un número:

1
2
3
4
5
6
7
8
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í, simplemente realizamos las comprobaciones en un bucle while:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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

Completemos una matriz y busquemos un elemento dentro de ella:

1
2
3
4
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:

1
2
3
4
5
6
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 grandes arreglos ordenados, o cuando planeamos buscar elementos repetidamente en un solo arreglo.

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 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.

If you'd like to read about Clasificación de algoritmos en Python, we've got you covered!