Binær søgning i Java: Rekursive, Iterative og Java-samlinger

Lineær søgning i Java har altid været den bedste metode til at finde et element i et array. Det søger efter hvert element i arrayet sekventielt og er ekstremt nemt at implementere. Men manglerne ved Linear Search er indlysende, når det pågældende array indeholder titusindvis af elementer. I sådanne tilfælde er "del og hersk" metoden implementeret af binær søgning meget mere effektiv og at foretrække for programmører med tid og rum kompleksitet i tankerne.

Binær søgning

I binær søgning opdeles et array gentagne gange i to halvdele, indtil nøglen (elementet, der søges i) er fundet. Opdelingen er virtuel, dvs. dataens integritet opretholdes. Ved hver iteration fokuseres den midterste værdi af arrayet. Hvis værdien er lig med den nøgle, vi leder efter, afsluttes løkken eller den rekursive funktion. Ellers bliver den ved med at sløjfe. Hvis den midterste værdi er større end nøglen, fokuserer funktionen så på den første halvdel af arrayet og omvendt. Denne proces gentages, indtil nøglen er fundet, eller hele arrayet er blevet itereret.

Forskellen mellem lineær og binær søgning

Binær søgealgoritme

Algoritmen for binær søgning er angivet nedenfor.

1. Bestem første og sidste punkt i arrayet. Punkterne vil blive justeret ved hver iteration i henhold til arrayet og den nøgle, der søges efter.
2. Gentag gennem arrayet og sammenlign den midterste værdi mellem dit nuværende første og sidste punkt. I den første iteration vil den første og den sidste variabel være den samme som de faktiske i arrayet.
3. Hvis nøglen er større end den midterste værdi, vil indekset for denne værdi blive gemt i den nye "Første" variabel.
4. Hvis nøglen er mindre end den midterste værdi, vil indekset for denne værdi blive gemt i 'Sidste' variabel.
5. Denne betingelse gentages, indtil en af ​​to betingelser bliver sande:
   • Nøglen er fundet.
   • Hele arrayet er blevet gentaget.

Koden for både iterativ binær søgning og rekursiv binær søgning er angivet nedenfor.

Iterativ binær søgning

Koden til binær søgning med en iterativ metode er angivet 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;
    }
}

Rekursiv binær søgning

Koden til binær brug af rekursion er angivet 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

Ved hver forbipasserende iteration deles arrayet, dvs. søgerummet, halvt. Efter hver iteration 'm' vil søgerummet ændre sig til en størrelse på N/2m. I værste fald vil vi kun stå tilbage med ét element på den anden side af arrayet. På dette tidspunkt vil kompleksiteten af ​​binær søgning være k = log2N. Tidskompleksiteten af ​​lineær søgning er O(N), hvilket resulterer i, at binær søgning er meget hurtigere med O(log2N) kompleksiteten. Dette er den primære fordel ved at bruge binær søgning frem for lineær søgning.

Rumkompleksitet

Binær søgning bruger tre forskellige variabler - start, slut og midt. Disse tre variable er skabt som pointere, der peger på hukommelsesplaceringen af ​​array-indekserne. På grund af dette er binær søgning ekstremt effektiv med plads. Rumkompleksiteten af ​​iterativ binær søgning er O(1). For rekursiv implementering er det O(log N).