Búsqueda binaria en Java: colecciones recursivas, iterativas y Java

La búsqueda lineal en Java siempre ha sido el método de acceso para encontrar un elemento en una matriz. Busca cada elemento de la matriz de forma secuencial y es extremadamente fácil de implementar. Sin embargo, las deficiencias de la búsqueda lineal son evidentes cuando la matriz en cuestión contiene decenas de miles de elementos. En tales casos, el método de "divide y vencerás" implementado por Binary Search es mucho más eficiente y preferible para los programadores que tienen en mente la complejidad del tiempo y el espacio.

Búsqueda binaria

En la búsqueda binaria, una matriz se divide repetidamente en dos mitades hasta que se encuentra la clave (elemento que se busca). La división es virtual, es decir, se mantiene la integridad de los datos. Con cada iteración, se enfoca el valor medio de la matriz. Si el valor es igual a la clave que estamos buscando, el ciclo o función recursiva termina. De lo contrario, sigue en bucle. Si el valor medio es mayor que la clave, la función se enfoca en la primera mitad de la matriz y viceversa. Este proceso se repite hasta que se encuentra la clave o se ha iterado toda la matriz.

Diferencia entre búsqueda lineal y binaria

Algoritmo de búsqueda binaria

El algoritmo de búsqueda binaria se proporciona a continuación.

1. Determine el primer y el último punto de la matriz. Los puntos se ajustarán en cada iteración según la matriz y la clave que se busca.
2. Iterar a través de la matriz y comparar el valor medio entre el primer y el último punto actual. En la primera iteración, la primera y la última variable serán las mismas que las reales en la matriz.
3. Si la clave es mayor que el valor medio, el índice de ese valor se almacenará en la nueva variable "Primera".
4. Si la clave es menor que el valor medio, el índice de ese valor se almacenará en la variable 'Última'.
5. Esta condición se repite hasta que se cumple una de dos condiciones:
   • Se encuentra la clave.
   • Se ha iterado toda la matriz.

El código para la búsqueda binaria iterativa y la búsqueda binaria recursiva se proporciona a continuación.

Búsqueda binaria iterativa

A continuación se proporciona el código para la búsqueda binaria con un método iterativo.

import java.util.Scanner;
public class IterativeBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
       
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
       
        int num = input.nextInt();
        int result = BinarySearchIterative(arr,num);
       
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
    public static int BinarySearchIterative(int[] arr, int num){
        //Representing the Start and End Index After Division of Array
        int start = 0;
        int end = arr.length;
 
        //Loop to Iterate Through the Array
        for(int i = 0; iarr[n]){
                start = n;
            }
            //If number to search for is greater than the arr value at index 'n'               
            else{
                end = n;
            }
        }
        //If number isn't found, return -1
        return -1;
    }
}

Búsqueda binaria recursiva

El código para Binary usando recursividad se da a continuación.

import java.util.Scanner;
public class RecursiveBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
 
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
 
        int num = input.nextInt();
        int result = BinarySearchRecursive(arr,0,arr.length-1,num);
 
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
    //Base Case to Exit the Recursive Function
    if (b < 1) {
        return -1;
    }
        int n = a + (b=1)/2;
 
       //If number is found at mean index of start and end
        if(arr[n]==num)
            return n;
 
       //If number to search for is greater than the arr value at index 'n'
        else if(arr[n]>num)
            return BinarySearchRecursive(arr,a,n-1,num);
 
       //If number to search for is greater than the arr value at index 'n'
        else
            return BinarySearchRecursive(arr,n+1,b,num);
    }
 
}

Complejidad del tiempo

Con cada iteración que pasa, la matriz, es decir, el espacio de búsqueda, se divide por la mitad. Después de cada iteración 'm', el espacio de búsqueda cambiará a un tamaño de N/2m. En el peor de los casos, solo nos quedará un elemento en un lado lejano de la matriz. En este momento, la complejidad de la búsqueda binaria será k = log2N. La complejidad temporal de la búsqueda lineal es O(N), lo que hace que la búsqueda binaria sea mucho más rápida con la complejidad O(log2N). Este es el principal beneficio de usar la búsqueda binaria sobre la búsqueda lineal.

Complejidad espacial

La búsqueda binaria utiliza tres variables diferentes: inicio, fin y medio. Estas tres variables se crean como punteros que apuntan a la ubicación de memoria de los índices de la matriz. Debido a esto, la búsqueda binaria es extremadamente eficiente con el espacio. La complejidad espacial de la búsqueda binaria iterativa es O(1). Para la implementación recursiva, es O (log N).