Búsqueda binaria

Introducción

Búsqueda

Una de las tareas que nos solemos encontrar con cierta frecuencia al programar es la de buscar la posición de un valor en un array.

Una primera aproximación es comparar cada elemento del array con el valor buscado de forma secuencial, hasta localizarlo. Pero esto no es muy eficiente: en el peor caso, si el array no contiene el valor buscado, tendremos que comparar todos los elementos del array.

Siempre es interesante y a menudo importante, optimizar los programas, es decir, minimizar el tiempo y recursos necesarios para realizar una tarea. Generalmente, las optimizaciones se dirigen primero a minimizar las subtareas que más se repiten, ya que de ese modo, incluso pequeñas optimizaciones, se traducen en mejores resultados, puesto que se suman con cada repetición. En el caso de búsquedas, intentaremos minimizar el número de comparaciones, y si es posible, el algoritmo de comparación.

Aquí es dónde entra el algoritmo de búsqueda binaria.

Algoritmo

Pero para empezar, hay que tener en cuenta que este algoritmo solo funciona con arrays ordenados. Por lo tanto, si el array no está ordenado, el primer paso será ordenarlo.

Imagina que nos plantean un juego que consiste en adivinar un número entre 1 y 1000, y cada vez que decimos un número, nos responden si el número a adivinar es mayor o menor.

En lugar de decir números al azar, con la esperanza de acertar, o de empezar a decir todos los números en orden secuencial, optaremos por una estrategia más inteligente:

Empezaremos por el número central del intervalo, el 500. Si nos dicen que el número a adivinar es mayor, sabemos que estará entre 501 y 1000, si es menor, entre 1 y 499.

Supongamos que es el primer caso, ahora elegiremos el número central del nuevo intermedio, que será el 750 o 751, (depende del redondeo).

Y seguiremos aplicando el mismo sistema hasta encontrar el número en cuestión.

El algoritmo de búsqueda binaria es similar, salvo que el conjunto de elementos en los que se realiza la búsqueda no tiene por qué tener todos los valores entre el primero y el último, e incluso puede tratarse de un dominio en el que existan infinitos valores posibles, por ejemplo, un array de palabras o de números en coma flotante.

Método

El método general parte de un array ordenado de menor a mayor. Puede haber elementos repetidos, pero si el valor buscado es uno de los repetidos, el algoritmo nos devolverá la posición de alguno de ellos, pero no necesariamente el primero o el último.

Esto es fácil de demostrar suponiendo un array en el que todos los elementos tienen el mismo valor. El algoritmo nos dará la posición central del array. Si un valor se repite tres veces, el algoritmo nos dará la posición del primero, segundo o tercero, dependiendo de las posiciones que ocupen dentro del array.

Si para nuestro programa en particular es importante obtener una posición concreta cuando el valor esté repetido, tendremos que añadir código después de aplicar el algoritmo.



    


  • Partimos de un array A con N elementos ordenados de menor a mayor, y buscaremos en ese array un valor V.
    • 


  • Estableceremos las posiciones límite inferior y superior: Li=0 y Ls=N-1.
    • 


  • Bucle: Mientras el rango tenga al menos un valor: Li<=Ls


      


    • Calculamos la posición central C entre Li y Ls: C=Li+(Ls-Li)/2.
      • 


    • Si la posición C contiene el valor V, hemos terminado. Si A[C] == V, retornamos C.
      • 


    • Si en la posición C el valor es mayor que V, asignamos un nuevo límite superior. Ls=C-1.
      • 


    • Si en la posición C el valor es menor que V, asignamos un nuevo límite inferior. Li=C+1.
      • 


    • Cerrar el bucle


    • 


  • Valor no encontrado. Retornamos un valor que lo indique, por ejemplo, -1.
    •

Aunque se puede implementar este algoritmo de forma recursiva, lo óptimo es hacerlo de forma iterativa.

En cuanto al valor de retorno, podemos devolver el valor del índice o un valor convenido si no se encuentra el valor objetivo, o podemos devolver un puntero al elemento y NULL si no se encuentra.

Ejemplo 1

Veamos un ejemplo para un array de enteros.

Nuestra función de búsqueda bBinaria requiere tres parámetros: el valor a buscar, la dirección del array, y el número de elementos que contiene.

El valor de retorno será el índice del elemento encontrado, o -1 si no se encuentra.


// Busqueda binaria

// 2022 C con Clase



#include <iostream>

const size_t nElementos = 10;



int bBinaria(int V, int *A, int N);



int main() {

    int A[nElementos] = {0,3,5,7,12,23,24,30,31,39};

    int V;

    int pos;



    V=12;

    pos = bBinaria(V, A, nElementos);

    if(pos>0) std::cout << "posicion de " << V << ": " << pos << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;

    V=24;

    pos = bBinaria(V, A, nElementos);

    if(pos>0) std::cout << "posicion de " << V << ": " << pos << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;

    V=39;

    pos = bBinaria(V, A, nElementos);

    if(pos>0) std::cout << "posicion de " << V << ": " << pos << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;

    V=22;

    pos = bBinaria(V, A, nElementos);

    if(pos>0) std::cout << "posicion de " << V << ": " << pos << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;



    return 0;

}



int bBinaria(int V, int *A, int N) {

    int Li, Ls, Lc;



    Li = 0;

    Ls = N-1;

    while(Li <= Ls) {

        Lc = Li+(Ls-Li)/2;

        if(A[Lc] == V) return Lc;

        if(A[Lc] > V) Ls = Lc-1;

        else Li = Lc+1;

    }

    return -1;

}

Ejemplo 2

Pero podemos ahorrarnos el trabajo de programar esta función, ya que la librería estándar stdlib ya dispone de una función que implementa la búsqueda binaria, generalizada para cualquier tipo de array: bsearch.


// Busqueda binaria

// 2022 C con Clase



#include <iostream>

#include <cstdlib>

const size_t nElementos = 10;



int comparar(const void *arg1, const void *arg2);



int main() {

    int A[nElementos] = {0,3,5,7,12,23,24,30,31,39};

    int V;

    int *pV;



    V=12;

    pV = (int*)bsearch(&V, A, nElementos, sizeof(int), comparar);

    if(pV) std::cout << "posicion de " << V << ": " << pV-A << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;

    V=24;

    pV = (int*)bsearch(&V, A, nElementos, sizeof(int), comparar);

    if(pV) std::cout << "posicion de " << V << ": " << pV-A << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;

    V=39;

    pV = (int*)bsearch(&V, A, nElementos, sizeof(int), comparar);

    if(pV) std::cout << "posicion de " << V << ": " << pV-A << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;

    V=22;

    pV = (int*)bsearch(&V, A, nElementos, sizeof(int), comparar);

    if(pV) std::cout << "posicion de " << V << ": " << pV-A << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;



    return 0;

}



int comparar(const void *arg1, const void *arg2) {

    return *(int*)arg1 - *(int*)arg2;

}

La función bsearch requiere cinco parámetros: el valor a buscar, un puntero al array, el número de elementos del array, el tamaño de cada elemento y un puntero a una función de comparación. El valor de retorno será un puntero al elemento localizado o NULL si no se encuentra.

El tamaño de cada elemento es necesario porque a diferencia de nuestro primer ejemplo, esta función puede trabajar con arrays de cualquier tipo, pero para ello trabaja con punteros genéricos, de tipo void. Este dato le permite obtener un puntero a un elemento a partir de su posición.

La función de comparación también es necesaria, ya que saber si un elemento es mayor o menor que el valor buscado depende del tipo del valor.

Esta función recibe dos parámetros, que son punteros a valores del mismo tipo que el que buscamos y que los elementos del array. Debe devolver un valor mayor que cero si el valor apuntado por el primer argumento es mayor que el apuntado por el segundo. Un valor menor que cero si el valor apuntado por el primer argumento se menor, y cero si son iguales.

En este ejemplo los valores son de tipo int, por lo que podemos optimizar esta función restando los valores apuntados por el primer y segundo argumentos.

Sería equivalente a esta otra versión:


int comparar(const void *arg1, const void *arg2) {

    if(*(int*)arg1 == *(int*)arg2) return 0

    else if(*(int*)arg1 < *(int*)arg2) return -1

    return 1;

}

Ejemplo 3

Veamos cómo usar esta misma función con un array de cadenas:


// Busqueda binaria

// 2022 C con Clase



#include <iostream>

#include <cstdlib>

#include <cstring>

const size_t nElementos = 10;

const size_t tam = 10;



int comparar(const void *arg1, const void *arg2);



int main() {

    char A[nElementos][tam] = {"Ave","Barco","Bruja","Colmena","Dado","Ducha","Fresa","Gallo","Hueco","Roma"};

    char V[tam];

    char *pV;



    std::strcpy(V, "Dado");

    pV = (char*)bsearch(&V, A, nElementos, tam, comparar);

    if(pV) std::cout << "posicion de " << V << ": " << (pV-(char*)&A[0])/tam << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;

    std::strcpy(V, "Barco");

    pV = (char*)bsearch(&V, A, nElementos, tam, comparar);

    if(pV) std::cout << "posicion de " << V << ": " << (pV-(char*)&A[0])/tam << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;

    std::strcpy(V, "Hueco");

    pV = (char*)bsearch(&V, A, nElementos, tam, comparar);

    if(pV) std::cout << "posicion de " << V << ": " << (pV-(char*)&A[0])/tam << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;

    std::strcpy(V, "Grano");

    pV = (char*)bsearch(&V, A, nElementos, tam, comparar);

    if(pV) std::cout << "posicion de " << V << ": " << (pV-(char*)&A[0])/tam << std::endl; 

    else std::cout << "Valor " << V << " No encontrado" << std::endl;



    return 0;

}



int comparar(const void *arg1, const void *arg2) {

    return std::strcmp((char*)arg1, (char*)arg2);

}

Bugs

Hay una anécdota curiosa sobre la implementación de este algoritmo en Java. Puedes ver un video sobre esto en Computerphille.

El bug se presentaba cuando se calcula el índice de la posición central C entre Li y Ls, aunque solo en ciertas circunstancias.

Al contrario que el algoritmo que hemos presentado en éste artículo, en Java ese valor se calculaba según la siguiente fórmula:


    Lc = (Li+Ls)/2;

En general no hay nada malo en este cálculo, y es equivalente al que hemos usado Lc = Li+(Ls-Li)/2;, pero en ciertas circunstancias puede producirse un error.

¿Cuáles son esas circunstancias? Bien se tienen que dar dos condiciones:

  1. Que el array tenga muchos elementos.
  2. Que el valor a buscar esté en un valor de índice grande.

¿Cómo de grande tiene que ser el array? Tanto como para que la suma del valor del último índice más el del índice intermedio supere la capacidad de un int.

Por ejemplo, supongamos que nuestros int son de 32 bits con signo, que nuestro array contiene 1.431.655.766 elementos, y que el valor a buscar es mayor que el que contiene la posición intermedia, con un índice 715.827.883, con lo que Li será 715.827.883. Para la segunda iteración, si calculamos el valor de Lc mediante la fórmula Lc = (Li+Ls)/2, primero se hará la suma: 715.827.883+1.431.655.766=2.147.483.649.

Pero el valor positivo más grande para un entero con signo de 32 bits es 2.147.483.647, de modo que en realidad el valor obtenido será un número negativo, concretamente el -2.147.483.647, que aunque lo dividamos entre 2 será un valor de índice no válido.

Con la fórmula que hemos usado en nuestro algoritmo esto no sucede, ya que primer se calcula la diferencia: Lc = Li+(Ls-Li)/2;, de modo que nunca provocaremos un desbordamiento del valor entero.

Me gustaría pensar que el algoritmo propuesto en este artículo tenía en cuenta este posible bug, pero no fue así, y ha sido una simple cuestión de suerte.