Binair zoeken in Java: recursieve, iteratieve en Java-collecties

Lineair zoeken in Java is altijd de beste methode geweest om een ​​element in een array te vinden. Het doorzoekt elk element van de array opeenvolgend en is uiterst eenvoudig te implementeren. De tekortkomingen van Lineair zoeken zijn echter duidelijk wanneer de betreffende array tienduizenden elementen bevat. In dergelijke gevallen is de door Binary Search geïmplementeerde "verdeel en heers"-methode een stuk efficiënter en te prefereren voor programmeurs die rekening houden met tijd- en ruimtecomplexiteit.

Binaire zoekopdracht

Bij binair zoeken wordt een array herhaaldelijk in twee helften verdeeld totdat de sleutel (het element dat wordt doorzocht) is gevonden. De divisie is virtueel, dwz de integriteit van de gegevens blijft behouden. Bij elke iteratie wordt de middelste waarde van de array gefocust. Als de waarde gelijk is aan de sleutel die we zoeken, eindigt de lus of recursieve functie. Anders blijft het maar herhalen. Als de middelste waarde groter is dan de sleutel, richt de functie zich op de eerste helft van de array en vice versa. Dit proces wordt herhaald totdat de sleutel is gevonden of de hele array is herhaald.

Verschil tussen lineair en binair zoeken

Binair zoekalgoritme

Het algoritme van Binary Search wordt hieronder gegeven.

1. Bepaal het eerste en laatste punt van de array. De punten worden bij elke iteratie aangepast volgens de array en de sleutel die wordt doorzocht.
2. Herhaal de reeks en vergelijk de middelste waarde tussen uw huidige eerste en laatste punt. In de eerste iteratie zullen de eerste en de laatste variabele dezelfde zijn als de werkelijke variabelen in de array.
3. Als de sleutel groter is dan de middelste waarde, wordt de index van die waarde opgeslagen in de nieuwe variabele "First".
4. Als de sleutel kleiner is dan de middelste waarde, wordt de index van die waarde opgeslagen in de variabele 'Laatste'.
5. Deze voorwaarde wordt herhaald totdat een van de volgende twee voorwaarden waar wordt:
   • Sleutel is gevonden.
   • De hele array is herhaald.

De code voor zowel iteratief binair zoeken als recursief binair zoeken wordt hieronder gegeven.

Iteratief binair zoeken

De code voor binair zoeken met een iteratieve methode wordt hieronder gegeven.

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

Recursief binair zoeken

De code voor binair gebruik van recursie wordt hieronder gegeven.

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

Tijd complexiteit

Bij elke iteratie die voorbijgaat, wordt de array, dwz de zoekruimte, gehalveerd. Na elke iteratie 'm' verandert de zoekruimte in een grootte van N/2m. In het slechtste geval houden we slechts één element over aan de ene kant van de array. Op dit moment is de complexiteit van binair zoeken k = log2N. De tijdcomplexiteit van lineair zoeken is O(N), wat ertoe leidt dat binair zoeken veel sneller gaat met de O(log2N)-complexiteit. Dit is het belangrijkste voordeel van binair zoeken in plaats van lineair zoeken.

Ruimtelijke complexiteit

Binair zoeken gebruikt drie verschillende variabelen: begin, einde en midden. Deze drie variabelen worden gemaakt als pointers die verwijzen naar de geheugenlocatie van de array-indices. Hierdoor is binair zoeken uiterst efficiënt met ruimte. De ruimtecomplexiteit van iteratief binair zoeken is O(1). Voor recursieve implementatie is het O(log N).