Binär sökning i Java: Rekursiva, Iterativa och Java-samlingar

Linjär sökning i Java har alltid varit den bästa metoden för att hitta ett element i en array. Den söker igenom varje element i arrayen sekventiellt och är extremt lätt att implementera. Bristerna med Linear Search är dock uppenbara när arrayen i fråga innehåller tiotusentals element. I sådana fall är metoden "dela och erövra" implementerad av Binary Search mycket effektivare och att föredra för programmerare med tid och rumskomplexitet i åtanke.

Binär sökning

I binär sökning delas en array upprepade gånger i två halvor tills nyckeln (elementet som genomsöks) hittas. Uppdelningen är virtuell, dvs dataintegriteten bibehålls. Med varje iteration fokuseras arrayens mittvärde. Om värdet är lika med nyckeln vi letar efter avslutas slingan eller den rekursiva funktionen. Annars fortsätter det att loopa. Om mittvärdet är större än nyckeln fokuserar funktionen på den första halvan av arrayen och vice versa. Denna process upprepas tills nyckeln hittas eller hela arrayen har itererats.

Skillnaden mellan linjär och binär sökning

Binär sökalgoritm

Algoritmen för binär sökning ges nedan.

1. Bestäm första och sista punkten i arrayen. Punkterna kommer att justeras vid varje iteration enligt arrayen och nyckeln som söks.
2. Iterera genom arrayen och jämför mittvärdet mellan din nuvarande första och sista punkt. I den första iterationen kommer den första och den sista variabeln att vara desamma som de faktiska i arrayen.
3. Om nyckeln är större än mittvärdet kommer indexet för det värdet att lagras i den nya variabeln "Första".
4. Om nyckeln är mindre än mittvärdet, kommer indexet för det värdet att lagras i variabeln 'Sista'.
5. Detta villkor upprepas tills ett av två villkor blir sant:
   • Nyckeln har hittats.
   • Hela arrayen har itererats.

Koden för både iterativ binär sökning och rekursiv binär sökning ges nedan.

Iterativ binär sökning

Koden för binär sökning med en iterativ metod ges nedan.

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ökning

Koden för binär användning av rekursion ges nedan.

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

Tidskomplexitet

För varje iteration som passerar delas arrayen, dvs sökutrymmet, till hälften. Efter varje iteration 'm' kommer sökutrymmet att ändras till en storlek på N/2m. I värsta fall kommer vi bara att ha ett element kvar på ena sidan av arrayen. Vid denna tidpunkt kommer komplexiteten för binär sökning att vara k = log2N. Tidskomplexiteten för linjär sökning är O(N) vilket resulterar i att binär sökning blir mycket snabbare med O(log2N) komplexiteten. Detta är den främsta fördelen med att använda binär sökning framför linjär sökning.

Rymdkomplexitet

Binär sökning använder tre olika variabler - start, slut och mitt. Dessa tre variabler skapas som pekare som pekar på minnesplatsen för arrayindexen. På grund av detta är binär sökning extremt effektiv med utrymme. Rymdkomplexiteten för iterativ binär sökning är O(1). För rekursiv implementering är det O(log N).