Búsqueda binaria en Java

B

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.

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad