B煤squeda binaria en Java

    Introducci贸n

    Desde elegir tus preciados jeans de tu guardarropa hasta elegir la pr贸xima pel铆cula para ver con tu pareja, la vida humana est谩 llena de buscar cosas.

    En la vida cotidiana, los humanos suelen buscar entre unos pocos elementos, si no una docena. Las computadoras tienen que lidiar con la b煤squeda de datos de cantidades comparativamente masivas en t茅rminos de tama帽o y cantidad.

    Esto justifica la necesidad de una computadora de tener un m茅todo eficiente para buscar dentro de sus matrices y colecciones de la manera m谩s eficiente posible.

    Poder 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

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

    Funciona sobre la base de dividir y conquistar al comparar el elemento de destino con el elemento medio 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 del medio) 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 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:

    Implementaci贸n

    Dado que tenemos un paso que se repite (verificar el elemento del medio y descartar la mitad de la matriz), podemos implementar el algoritmo usando dos enfoques: un enfoque iterativo y un enfoque recursivo.

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

    Iterativo

    Comencemos con la implementaci贸n iterativa:

    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 hacer un seguimiento de lowIndex (el primer 铆ndice) y el highIndex (煤ltimo 铆ndice) para obtener el medio aritm茅tico de la matriz. los elementPos por defecto es -1 lo que significa que no se ha encontrado el elemento.

    Si no es as铆, simplemente devolvemos esta posici贸n. Si es as铆, ajustamos el elementPos para reflejar la ubicaci贸n en la matriz.

    Entonces, a trav茅s de un while loop, comprobamos si el elemento del medio es el que estamos buscando. Si no, ajustamos el lowIndex y highIndex para ignorar la mitad de la matriz en la que no est谩 el elemento de destino.

    Recursivo

    La implementaci贸n recursiva tambi茅n es bastante sencilla, pero simplemente llamamos al m茅todo de forma recursiva hasta que se haya encontrado el elemento:

    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;
    }
    

    B煤squeda binaria de evaluaci贸n comparativa

    Para analizar qu茅 tan eficientemente funciona el algoritmo de b煤squeda binaria con conjuntos de datos enteros dados, ejecutemos el c贸digo contra matrices de n煤meros enteros de tama帽os variados y observemos los tiempos de ejecuci贸n necesarios para que una b煤squeda binaria encuentre un n煤mero dado, expresado en nanosegundos:

    Tama帽o de matriz 1.a ejecuci贸n (ns) 2.a ejecuci贸n (ns) 3.a ejecuci贸n (ns) Promedio (ns)

    10568,500755.000644,700656,066
    100846,100713 000724,100761,066
    10001.323.600942,900735,8001,000,766

    An谩lisis Big-O

    En cada una de sus iteraciones de b煤squeda, la b煤squeda binaria divide a la mitad el conjunto de elementos que busca. Esto lleva al algoritmo de b煤squeda binaria a retener una eficiencia de tiempo logar铆tmico en el peor de los casos. En t茅rminos de notaci贸n Big-O, un O (log n) complejidad.

    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 la b煤squeda binaria tiene la mejor eficiencia de caso 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 eficaz para buscar matrices, su l贸gica requiere que la matriz buscada se ordene de antemano.

    En caso de que planee utilizar el algoritmo en una matriz sin clasificar, primero tendr谩 que ordenarlo, lo que aumentar谩 la complejidad. En este caso, incluso una b煤squeda lineal t铆pica dominar铆a la b煤squeda binaria con su En) complejidad.

    Conclusi贸n

    Desde que fue mencionado por primera vez en 1946 por John Mauchly, Binary Search se ha conservado hasta la fecha como un algoritmo f谩cil de entender y altamente eficiente para buscar matrices ordenadas para las posiciones de sus elementos de destino.

    Funciona sobre la base de dividir y conquistar al comparar el elemento de destino con el elemento medio de la matriz. En este art铆culo, hemos implementado los enfoques iterativo y recursivo y comparamos el algoritmo con tres conjuntos diferentes de enteros.

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

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *