Binært søk i Java: Rekursive, Iterative og Java-samlinger

Lineært søk i Java har alltid vært go-to-metoden for å finne et element i en matrise. Den søker etter hvert element i arrayet sekvensielt og er ekstremt enkelt å implementere. Manglene ved Linear Search er imidlertid åpenbare når den aktuelle matrisen inneholder titusenvis av elementer. I slike tilfeller er "del og hersk"-metoden implementert av Binary Search mye mer effektiv og å foretrekke for programmerere med tid og romkompleksitet i tankene.

Binært søk

I binært søk blir en matrise gjentatte ganger delt i to halvdeler til nøkkelen (elementet som det søkes i) er funnet. Inndelingen er virtuell, dvs. at integriteten til dataene opprettholdes. Med hver iterasjon blir den midterste verdien av matrisen fokusert. Hvis verdien er lik nøkkelen vi leter etter, avsluttes løkken eller den rekursive funksjonen. Ellers fortsetter det å sløyfe. Hvis den midterste verdien er større enn nøkkelen, fokuserer funksjonen på den første halvdelen av matrisen og omvendt. Denne prosessen gjentas til nøkkelen er funnet eller hele matrisen har blitt iterert.

Forskjellen mellom lineært og binært søk

Binær søkealgoritme

Algoritmen til binært søk er gitt nedenfor.

1. Bestem første og siste punkt i matrisen. Punktene vil bli justert ved hver iterasjon i henhold til matrisen og nøkkelen som søkes.
2. Iterer gjennom matrisen og sammenlign den midterste verdien mellom ditt nåværende første og siste punkt. I den første iterasjonen vil den første og den siste variabelen være den samme som de faktiske i matrisen.
3. Hvis nøkkelen er større enn den midterste verdien, vil indeksen til den verdien bli lagret i den nye "First"-variabelen.
4. Hvis nøkkelen er mindre enn den midterste verdien, vil indeksen til den verdien bli lagret i 'Siste'-variabelen.
5. Denne tilstanden gjentas til en av to betingelser blir sann:
   • Nøkkelen er funnet.
   • Hele matrisen har blitt iterert.

Koden for både iterativt binært søk og rekursivt binært søk er gitt nedenfor.

Iterativt binært søk

Koden for binært søk med en iterativ metode er gitt nedenfor.

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

Rekursivt binært søk

Koden for binær bruk av rekursjon er gitt nedenfor.

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

Tidskompleksitet

For hver forbigående iterasjon deles matrisen, dvs. søkeområdet, halvparten. Etter hver iterasjon 'm' vil søkeområdet endres til en størrelse på N/2m. I verste fall vil vi bare sitte igjen med ett element på den andre siden av matrisen. På dette tidspunktet vil kompleksiteten til binært søk være k = log2N. Tidskompleksiteten til lineært søk er O(N) som resulterer i at binært søk blir mye raskere med O(log2N) kompleksiteten. Dette er den primære fordelen med å bruke binært søk fremfor lineært søk.

Plass kompleksitet

Binært søk bruker tre forskjellige variabler - start, slutt og midt. Disse tre variablene lages som pekere som peker til minneplasseringen til matriseindeksene. På grunn av dette er binært søk ekstremt effektivt med plass. Romkompleksiteten til iterativt binært søk er O(1). For rekursiv implementering er det O(log N).