Búsqueda binaria en Java

Binary Search es un algoritmo de búsqueda realmente simple pero efectivo. En este artículo, implementaremos la búsqueda binaria iterativa y recursiva en Java y analizaremos su rendimiento.

Introducción

Desde elegir su preciado par de jeans de su guardarropa hasta elegir la próxima película para ver con su pareja, la vida humana está llena de búsqueda de cosas.

Mientras que en la vida cotidiana, los humanos generalmente buscan entre unos pocos, si no una docena, de elementos. Las computadoras tienen que lidiar con la búsqueda a través de datos de cantidades comparativamente masivas en términos de su tamaño y cantidad.

Esto justifica la necesidad de una computadora de tener un método eficiente para buscar dentro de sus arreglos y colecciones de la manera más eficiente posible.

Ser capaz de encontrar información en medio de una colección es uno de los puntos funcionales más básicos de una aplicación.

Búsqueda binaria

Búsqueda binaria (a veces conocida como Búsqueda logarítmica) es un algoritmo muy popular para buscar en una matriz ordenada la posición de un elemento determinado.

Funciona sobre la base de divide y vencerás al comparar el elemento objetivo con el elemento central de la matriz. En caso de que se encuentre una coincidencia, se devuelve su posición; de lo contrario, si el elemento de destino es más pequeño que el elemento del medio, no puede estar en el lado derecho del elemento del medio.

Por lo tanto, la mitad derecha de la matriz (incluido el elemento central) se descarta y la búsqueda continúa en la mitad izquierda utilizando el mismo enfoque.

De manera similar, en caso de que el elemento de destino sea más grande que el elemento del medio, no puede estar en un lugar anterior al medio de la matriz. Por lo tanto, la mitad izquierda de la matriz se descarta y la búsqueda continúa en la mitad derecha.

Esto se repite hasta que se encuentra una coincidencia.

Podemos hacer esta suposición simplemente porque sabemos que la matriz está ordenada de antemano. Si no estuviera ordenado, no podríamos implementar la búsqueda binaria.

Aquí hay una representación visual de cómo funciona la búsqueda binaria:

binary search

Implementación

Dado que tenemos un paso repetitivo (comprobar el elemento central y descartar la mitad de la matriz), podemos implementar el algoritmo utilizando dos enfoques: un enfoque iterativo y un enfoque recursivo.

Como de costumbre, no hay un ganador claro entre estos dos y puede optar por utilizar cualquiera de ellos según sus preferencias personales.

Iterativo

Empecemos con la implementación iterativa:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int iterativeSearch(int[] arrayToSearch, int element) {
    int lowIndex = 0;
    int highIndex = arrayToSearch.length-1;

    // Holds the position in array for given element
    // Initial negative integer set to be returned if no match was found on array
    int elementPos = -1;

    // If lowIndex less than highIndex, there's still elements in the array
    while (lowIndex <= highIndex) {
        int midIndex = (lowIndex + highIndex) / 2;
        if (element == arrayToSearch[midIndex]) {
            elementPos = midIndex;
            break;
        } else if (element < arrayToSearch[midIndex]) {
            highIndex = midIndex-1;
        } else if (element > arrayToSearch[midIndex]) {
            lowIndex = midIndex+1;
        }
    }
    return elementPos;
}

Necesitamos realizar un seguimiento de lowIndex (el primer índice) y highIndex (último índice) para obtener el medio aritmético de la matriz. El elementPos por defecto es -1 lo que significa que el elemento no ha sido encontrado.

Si no es así, simplemente devolvemos esta posición. Si es así, ajustamos elementPos para reflejar la ubicación en la matriz.

Luego, a través de un bucle while, verificamos si el elemento del medio es el que estamos buscando. Si no, ajustamos lowIndex y highIndex para ignorar la mitad de la matriz en la que no se encuentra el elemento de destino.

Recursivo

La implementación recursiva también es bastante sencilla, pero simplemente llamamos al método recursivamente hasta que se encuentra el elemento:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int recursiveSearch(int[] arrayToSearch, int element) {
    return recursiveSearch(arrayToSearch, element, 0, arrayToSearch.length-1);
}

private static int recursiveSearch(int[] arrayToSearch, int element, int lowIndex, int highIndex) {
    // If lowIndex surpasses highIndex, the element has not been found
    if (lowIndex > highIndex) return -1;

    // Default assumption is that the element is not found
    int elementPos = -1;

    int midIndex = (lowIndex + highIndex) / 2;

    if (element == arrayToSearch[midIndex]) {
        elementPos = midIndex;
    } else if (element < arrayToSearch[midIndex]) {
        recursiveSearch(arrayToSearch, element, lowIndex, midIndex-1);
    } else if (element > arrayToSearch[midIndex]) {
        recursiveSearch(arrayToSearch, element, midIndex+1, highIndex);
    }
    return elementPos;
}

Benchmarking Binary Search

Para analizar qué tan eficientemente funciona el algoritmo de búsqueda binaria con conjuntos de datos de enteros dados, ejecutemos el código contra matrices de enteros de varios tamaños y observemos los tiempos de ejecución necesarios para que una búsqueda binaria encuentre un número determinado, expresado en nanosegundos:


Tamaño de matriz 1.ª ejecución (ns) 2.ª ejecución (ns) 3.ª ejecución (ns) Promedio (ns) 10 568.500 755.000 644.700 656.066 100 846.100 713.000 724.100 761.066 1000 1.323.600 942.900 735.800 1.000.766


Análisis O grande

En cada una de sus iteraciones de búsqueda, Binary Search reduce a la mitad el conjunto de elementos que busca. Esto hace que el algoritmo de búsqueda binaria conserve una eficiencia en el peor de los casos de tiempo logarítmico. En Términos de notación Big-O, una complejidad O(log n).

Más aún, en caso de que el elemento de destino se encontrara en el medio de la matriz en el primer intento, la operación se habría completado en tiempo lineal. De eso podemos deducir que Binary Search tiene una eficiencia en el mejor de los casos de O(1).

Por lo tanto, de manera concluyente, el algoritmo de búsqueda binaria tiene un rendimiento promedio de O(log n) .

También es fundamental mencionar que, aunque el algoritmo es muy efectivo para buscar matrices, su lógica requiere que la matriz buscada se ordene de antemano.

En caso de que planee usar el algoritmo en una matriz no ordenada, primero tendrá que ordenarla, lo que provocará una mayor complejidad. En este caso, incluso una búsqueda lineal típica normalmente dominaría la búsqueda binaria con su complejidad O(n).

Conclusión

Desde que [Juan Mauchly] (https://en.wikipedia.org/wiki/John_Mauchly) lo mencionó por primera vez en 1946, la búsqueda binaria se ha conservado hasta la fecha como un algoritmo de búsqueda fácil de entender y altamente eficiente. matrices ordenadas para las posiciones de sus elementos de destino.

Funciona sobre la base de divide y vencerás al comparar el elemento objetivo con el elemento central de la matriz. En este artículo, implementamos los enfoques iterativo y recursivo y comparamos el algoritmo con tres conjuntos diferentes de enteros.

Además, hemos realizado un análisis Big-O rápido para demostrar la eficiencia de este algoritmo de búsqueda básico pero efectivo.