Das Meistern der Binärsuche in Java

Einführung

Der binäre Suchalgorithmus ist ein effizienter Suchalgorithmus, der verwendet wird, um einen Wert in einem sortierten Array zu finden. Er ist schneller als die lineare Suche, da er in jeder Iteration die Hälfte des Arrays eliminiert. In diesem Lab werden wir die Schritte lernen, um den binären Suchalgorithmus in Java zu implementieren.

Erstellen eines sortierten Arrays

Der binäre Suchalgorithmus erfordert ein sortiertes Array, daher werden wir zunächst ein sortiertes Array erstellen.

int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

Implementieren des binären Suchalgorithmus iterativ

Wir werden nun den binären Suchalgorithmus iterativ implementieren. Diese Methode gibt den Index des Elements zurück, wenn es im Array vorhanden ist. Andernfalls gibt sie -1 zurück.

public static int binarySearchIterative(int[] sortedArray, int key) {
    int leftIdx = 0;
    int rightIdx = sortedArray.length - 1;
    while (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            rightIdx = midIdx - 1;
        } else
            leftIdx = midIdx + 1;
    }
    return -1;
}

Um den Code auszuführen, müssen wir zunächst die binarySearchIterative-Methode aufrufen und sortedArray und das Element, das wir suchen möchten, als Parameter übergeben.

## Kompilieren der Java-Datei
javac BinarySearch.java

## Ausführen der Datei
java BinarySearch

Implementieren des binären Suchalgorithmus rekursiv

Wir werden nun den binären Suchalgorithmus rekursiv implementieren. Diese Methode gibt ebenfalls den Index des Elements zurück, wenn es im Array vorhanden ist. Andernfalls gibt sie -1 zurück.

public static int binarySearchRecursive(int[] sortedArray, int key, int leftIdx, int rightIdx) {
    if (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            return binarySearchRecursive(sortedArray, key, leftIdx, midIdx - 1);
        } else
            return binarySearchRecursive(sortedArray, key, midIdx + 1, rightIdx);
    } else
        return -1;
}

Um den Code auszuführen, müssen wir die binarySearchRecursive-Methode aufrufen und sortedArray, das Element, das wir suchen möchten, leftIdx und rightIdx als Parameter übergeben.

Verwenden von eingebauten Methoden für den binären Suchalgorithmus

Java hat auch eingebaut Funktionen, um den binären Suchalgorithmus zu implementieren. Diese Funktionen sind Arrays.binarySearch() und Collections.binarySearch(). Wir können diese Funktionen verwenden, um ein Element in einem sortierten Array zu suchen.

Die Arrays.binarySearch()-Funktion nimmt ein sortiertes Array und einen Schlüsselwert zum Suchen als Parameter. Die Funktion gibt den Index des Schlüssels zurück, wenn er im Array vorhanden ist. Andernfalls gibt sie -1 zurück.

int index = Arrays.binarySearch(sortedArray, 6);

Die Collections.binarySearch()-Funktion kann auf Collections wie ArrayLists verwendet werden, um ein Element zu suchen. Die Funktion nimmt die sortierte Collection und einen Schlüssel als Parameter und gibt den Index zurück, an dem der Schlüssel vorhanden ist. Andernfalls gibt sie -1 zurück.

ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
int index = Collections.binarySearch(sortedList, 6);

Test

Wir werden nun alle Methoden testen und das Ergebnis ausgeben.

public static void main(String[] args) {
    int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int key = 12;
    System.out.println("Element " + key + " ist an Index vorhanden: " + binarySearchIterative(sortedArray, key));
    System.out.println("Element " + key + " ist an Index vorhanden: " + binarySearchRecursive(sortedArray, key, 0, sortedArray.length - 1));
    System.out.println("Element " + key + " ist an Index vorhanden: " + Arrays.binarySearch(sortedArray, key));
    ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
    System.out.println("Element " + key + " ist an Index vorhanden: " + Collections.binarySearch(sortedList, key));
}

Um den Code auszuführen, kompilieren wir zunächst das Java-Programm.

javac BinarySearch.java

Dann können wir das Programm ausführen.

java BinarySearch

Zusammenfassung

In diesem Lab wurden die Schritte behandelt, die erforderlich sind, um den binären Suchalgorithmus iterativ und rekursiv in der Programmiersprache Java zu implementieren. Wir haben uns auch mit den eingebauten Methoden Arrays.binarySearch() und Collections.binarySearch() zur Implementierung des binären Suchs kennengelernt. Wir haben ein sortiertes Array erstellt und verschiedene Methoden verwendet, um darin nach Elementen zu suchen.

Java-Binärsuche