Algoritmo de búsqueda binaria con EJEMPLO

Antes de aprender sobre la búsqueda binaria, aprendamos qué es la búsqueda.

¿Qué es la búsqueda?

La búsqueda es una utilidad que permite al usuario encontrar documentos, archivos, medios o cualquier otro tipo de datos contenidos en una base de datos. La búsqueda funciona según el principio simple de hacer coincidir los criterios con los registros y mostrárselos al usuario. De esta forma funciona la función de búsqueda más básica.

¿Qué es la búsqueda binaria?

Una búsqueda binaria es un tipo avanzado de algoritmo de búsqueda que encuentra y recupera datos de una lista ordenada de elementos. Su principio de funcionamiento básico consiste en dividir los datos de la lista por la mitad hasta que se localiza el valor requerido y se muestra al usuario en el resultado de la búsqueda. La búsqueda binaria se conoce comúnmente como un búsqueda de medio intervalo búsqueda logarítmica.

¿Cómo funciona la búsqueda binaria?

La búsqueda binaria funciona de la siguiente manera:

• El proceso de búsqueda se inicia localizando el elemento central del conjunto de datos ordenado.
• Después de eso, el valor de la clave se compara con el elemento.
• Si el valor de la clave es menor que el elemento central, la búsqueda analiza los valores superiores al elemento central para compararlos y encontrar coincidencias.
• En caso de que el valor de la clave sea mayor que el elemento central, la búsqueda analiza los valores inferiores al elemento central para compararlos y encontrar coincidencias.

Algoritmo de búsqueda binaria (pseudocódigo)

La búsqueda binaria se puede escribir como una rutina iterativa corta. Mantiene dos punteros, uno bajo y otro alto, y reduce el rango hasta que se encuentra el objetivo o el rango queda vacío.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

La rutina devuelve el índice del objetivo si tiene éxito y -1 si el valor no está presente. Dado que el rango se reduce a la mitad en cada iteración, el bucle se ejecuta como máximo log₂(n) veces.

Ejemplo de búsqueda binaria

Veamos el ejemplo de un diccionario. Si se necesita encontrar una palabra determinada, nadie recorre cada palabra de manera secuencial, sino que ubica aleatoriamente las palabras más cercanas para buscar la palabra requerida.

La imagen de arriba ilustra lo siguiente:

1. Tiene una matriz de 10 dígitos y es necesario encontrar el elemento 59.
2. Todos los elementos están marcados con un índice del 0 al 9. Ahora, se calcula el punto medio del array. Para ello, se toman los dos extremos del índice y se dividen entre 2. El resultado es 4.5, pero se aplica la parte entera. Por lo tanto, el punto medio es 4.
3. El algoritmo descarta todos los elementos desde el medio (4) hasta el límite inferior, porque 59 es mayor que 24, y ahora el arreglo se queda con solo 5 elementos.
4. Ahora bien, 59 es mayor que 45 y menor que 63. El valor central es 7. Por lo tanto, el valor del índice derecho se convierte en el valor central menos 1, que es igual a 6, y el valor del índice izquierdo permanece igual que antes, que es 5.
5. En este punto, sabes que 59 viene después de 45. Por lo tanto, el índice izquierdo, que es 5, también se convierte en medio.
6. Estas iteraciones continúan hasta que la matriz se reduce a un solo elemento, o el elemento a encontrar se convierte en el centro de la matriz.

Ejemplo

Veamos el siguiente ejemplo para comprender cómo funciona la búsqueda binaria.

1. Tiene una serie de valores ordenados que van del 2 al 20 y necesita ubicar 18.
2. El promedio de los límites inferior y superior es (l + r) / 2 = 4. El valor que se busca es mayor que el punto medio, que es 4.
3. Los valores de la matriz menores que el valor medio se descartan de la búsqueda, y los valores mayores que el valor medio 4 se buscan.
4. Este es un proceso de división recurrente hasta que se encuentra el elemento real que se va a buscar.

¿Por qué necesitamos la búsqueda binaria?

Las siguientes razones hacen que la búsqueda binaria sea una mejor opción para ser utilizada como algoritmo de búsqueda:

• La búsqueda binaria funciona de manera eficiente con datos ordenados, independientemente del tamaño de los datos.
• En lugar de realizar la búsqueda revisando los datos en una secuencia, el algoritmo binario accede aleatoriamente a los datos para encontrar el elemento requerido. Esto hace que los ciclos de búsqueda sean más cortos y precisos.
• La búsqueda binaria realiza comparaciones de los datos ordenados basándose en un principio de ordenación, en lugar de utilizar comparaciones de igualdad, que son más lentas y, en su mayoría, imprecisas.
• Tras cada ciclo de búsqueda, el algoritmo divide el tamaño del array por la mitad; por lo tanto, en la siguiente iteración, trabajará únicamente con la mitad restante del array.

Aprende nuestro próximo tutorial sobre Búsqueda lineal: Python, C++ Ejemplo.

Búsqueda binaria frente a búsqueda lineal

La búsqueda binaria y la búsqueda lineal son las dos formas más comunes de encontrar un valor en una colección. La siguiente tabla muestra sus diferencias:

En resumen, la búsqueda binaria es mucho más rápida con grandes conjuntos de datos ordenados, mientras que la búsqueda lineal es más sencilla y la única opción cuando los datos no están ordenados.

Preguntas Frecuentes