Metodo De Busqueda Binaria En Java

El método de búsqueda binaria es un algoritmo muy eficiente para encontrar un elemento dentro de un array ordenado. Su eficiencia radica en reducir a la mitad el espacio de búsqueda en cada paso. Aquí te explico cómo implementarlo en Java, paso a paso.

Paso 1: Preparación del entorno

Primero, necesitas un array ordenado. Este es un requisito fundamental para que la búsqueda binaria funcione correctamente. Crearemos un ejemplo sencillo para ilustrar el proceso. También necesitamos un valor a buscar dentro de este array.

Aquí tienes un ejemplo en Java:

public class BusquedaBinaria {
    public static void main(String[] args) {
        int[] numeros = {2, 5, 7, 8, 11, 12};
        int valorBuscado = 13; // Valor que queremos encontrar
        int indice = busquedaBinaria(numeros, valorBuscado);

        if (indice == -1) {
            System.out.println("El elemento " + valorBuscado + " no se encuentra en el array.");
        } else {
            System.out.println("El elemento " + valorBuscado + " se encuentra en el índice " + indice);
        }
    }

Paso 2: Implementación de la función de búsqueda binaria

Ahora, definiremos la función busquedaBinaria. Esta función tomará el array ordenado y el valor a buscar como parámetros. Devolverá el índice del valor buscado si lo encuentra, o -1 si no está presente.

Aquí tienes la función completa:

    public static int busquedaBinaria(int[] array, int valor) {
        int izquierda = 0;
        int derecha = array.length - 1;

        while (izquierda <= derecha) {
            int medio = izquierda + (derecha - izquierda) / 2; // Evita overflow

            if (array[medio] == valor) {
                return medio; // Se encontró el valor
            }

            if (array[medio] < valor) {
                izquierda = medio + 1; // El valor está en la mitad derecha
            } else {
                derecha = medio - 1; // El valor está en la mitad izquierda
            }
        }

        return -1; // El valor no se encuentra en el array
    }
}

Paso 3: Inicialización de variables

Dentro de la función, inicializamos dos variables: izquierda y derecha. izquierda apunta al inicio del array (índice 0). derecha apunta al final del array (índice array.length - 1).

Estas variables definirán el rango de búsqueda.

Paso 4: Bucle principal

Usamos un bucle while que se ejecuta mientras izquierda sea menor o igual que derecha. Esto significa que todavía hay elementos en el rango de búsqueda.

Dentro del bucle, calculamos el índice del elemento medio: medio = izquierda + (derecha - izquierda) / 2. Esta forma de calcular el medio ayuda a evitar un posible overflow cuando izquierda y derecha son números muy grandes.

Paso 5: Comparación del valor medio

Comparamos el valor del elemento en el índice medio con el valor buscado (valor). Si son iguales, encontramos el valor y retornamos el índice medio.

Si el valor en el índice medio es menor que el valor buscado, significa que el valor buscado (si existe) debe estar en la mitad derecha del array. Por lo tanto, actualizamos izquierda a medio + 1.

Si el valor en el índice medio es mayor que el valor buscado, significa que el valor buscado (si existe) debe estar en la mitad izquierda del array. Actualizamos derecha a medio - 1.

Paso 6: Valor no encontrado

Si el bucle while termina y no encontramos el valor buscado, significa que no está presente en el array. En este caso, retornamos -1 para indicar que el valor no fue encontrado.

Ejemplo: Búsqueda del número 11

Si buscamos el número 11 en el array {2, 5, 7, 8, 11, 12}, la búsqueda binaria lo encontrará en el índice 4. La búsqueda binaria divide el array a la mitad repetidamente until se encuentra el valor deseado.

Ejemplo: Búsqueda del número 13

Si buscamos el número 13 en el array {2, 5, 7, 8, 11, 12}, la búsqueda binaria terminará el bucle sin encontrarlo, y devolverá -1.