Binäre Suche in Java: Rekursive, iterative und Java-Sammlungen

Die lineare Suche in Java war schon immer die Methode der Wahl, um ein Element in einem Array zu finden. Es durchsucht nacheinander jedes Element des Arrays und ist äußerst einfach zu implementieren. Die Mängel der linearen Suche werden jedoch offensichtlich, wenn das betreffende Array Zehntausende von Elementen enthält. In solchen Fällen ist die von Binary Search implementierte Methode „Teile und herrsche“ viel effizienter und für Programmierer mit Blick auf die zeitliche und räumliche Komplexität vorzuziehen.

Binäre Suche

Bei der binären Suche wird ein Array wiederholt in zwei Hälften geteilt, bis der Schlüssel (das gesuchte Element) gefunden wird. Die Aufteilung erfolgt virtuell, dh die Integrität der Daten bleibt erhalten. Bei jeder Iteration wird der mittlere Wert des Arrays fokussiert. Wenn der Wert dem gesuchten Schlüssel entspricht, wird die Schleife oder rekursive Funktion beendet. Andernfalls läuft die Schleife weiter. Wenn der mittlere Wert größer als der Schlüssel ist, konzentriert sich die Funktion auf die erste Hälfte des Arrays und umgekehrt. Dieser Vorgang wird wiederholt, bis der Schlüssel gefunden oder das gesamte Array iteriert wurde.

Unterschied zwischen linearer und binärer Suche

Binärer Suchalgorithmus

Der Algorithmus der binären Suche ist unten angegeben.

1. Bestimmen Sie den ersten und letzten Punkt des Arrays. Die Punkte werden bei jeder Iteration entsprechend dem Array und dem gesuchten Schlüssel angepasst.
2. Durchlaufen Sie das Array und vergleichen Sie den Mittelwert zwischen Ihrem aktuellen ersten und letzten Punkt. In der ersten Iteration sind die erste und die letzte Variable mit den tatsächlichen Variablen im Array identisch.
3. Wenn der Schlüssel größer als der Mittelwert ist, wird der Index dieses Werts in der neuen Variablen „First“ gespeichert.
4. Wenn der Schlüssel kleiner als der mittlere Wert ist, wird der Index dieses Werts in der Variablen „Last“ gespeichert.
5. Diese Bedingung wird wiederholt, bis eine von zwei Bedingungen wahr wird:
   • Schlüssel ist gefunden.
   • Das gesamte Array wurde iteriert.

Der Code für die iterative Binärsuche und die rekursive Binärsuche ist unten angegeben.

Iterative binäre Suche

Der Code für die binäre Suche mit einer iterativen Methode ist unten angegeben.

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

Rekursive binäre Suche

Der Code für Binär mit Rekursion ist unten angegeben.

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

Zeitkomplexität

Bei jeder durchlaufenen Iteration wird das Array, also der Suchraum, zur Hälfte geteilt. Nach jeder Iteration „m“ ändert sich der Suchraum auf eine Größe von N/2m. Im schlimmsten Fall bleibt nur noch ein Element auf der anderen Seite des Arrays übrig. Zu diesem Zeitpunkt beträgt die Komplexität der binären Suche k = log2N. Die zeitliche Komplexität der linearen Suche beträgt O(N), was dazu führt, dass die binäre Suche mit der Komplexität O(log2N) viel schneller ist. Dies ist der Hauptvorteil der binären Suche gegenüber der linearen Suche.

Weltraumkomplexität

Die binäre Suche verwendet drei verschiedene Variablen – Start, Ende und Mitte. Diese drei Variablen werden als Zeiger erstellt, die auf den Speicherort der Array-Indizes zeigen. Aus diesem Grund ist die binäre Suche äußerst platzsparend. Die räumliche Komplexität der iterativen binären Suche beträgt O(1). Für die rekursive Implementierung ist es O(log N).