So implementieren Sie einen binären Suchalgorithmus in Java ohne Rekursion

Eine iterative Implementierung des beliebten binären Suchalgorithmus zum Auffinden eines Elements in einem sortierten Array.

Hallo zusammen! Ich habe viele Algorithmen und Artikel zur Datenstruktur in meinem Blog veröffentlicht, aber dieser ist der erste hier. In diesem Artikel werden beliebte grundlegende Algorithmen für Interviews untersucht.

Ja, Sie haben es richtig erraten: Sie müssen eine binäre Suche in Java implementieren und sowohl iterative als auch rekursive binäre Suchalgorithmen schreiben.

In der Informatik ist eine binäre Suche oder Halbintervallsuche ein Divide-and-Conquer-Algorithmus , der die Position eines Elements in einem sortierten Array lokalisiert. Bei der binären Suche wird ein Eingabewert mit dem mittleren Element des Arrays verglichen.

Der Vergleich bestimmt, ob das Element der Eingabe entspricht, kleiner als die Eingabe oder größer als die Eingabe ist.

Wenn das zu vergleichende Element der Eingabe entspricht, stoppt die Suche und gibt normalerweise die Position des Elements zurück.

Wenn das Element nicht gleich der Eingabe ist, wird ein Vergleich durchgeführt, um festzustellen, ob die Eingabe kleiner oder größer als das Element ist.

Abhängig vom Ergebnis startet der Algorithmus dann erneut, durchsucht jedoch nur die obere oder untere Teilmenge der Elemente des Arrays.

Wenn sich die Eingabe nicht im Array befindet, gibt der Algorithmus normalerweise einen eindeutigen Wert aus, der dies wie -1 angibt, oder löst einfach eine RuntimeException in Java wie NoValueFoundException aus.

Binäre Suchalgorithmen halbieren normalerweise die Anzahl der zu überprüfenden Elemente bei jeder aufeinanderfolgenden Iteration, wodurch das angegebene Element in logarithmischer Zeit lokalisiert wird (oder seine Abwesenheit bestimmt wird).

Übrigens, wenn Sie nicht mit grundlegenden Such- und Sortieralgorithmen vertraut sind, können Sie auch an einem Kurs wie Datenstrukturen und Algorithmen: Deep Dive mit Java teilnehmen , um grundlegende Algorithmen zu erlernen.

Wenn Sie sich nicht für Java entscheiden, finden Sie in dieser Liste der Algorithmenkurse weitere Empfehlungen für JavaScript und Python.

Übrigens, wenn Sie Bücher bevorzugen, empfehle ich Ihnen, ein umfassendes Algorithmusbuch wie Introduction to Algorithms von Thomas H. Cormen zu lesen .

Hier ist ein Beispielcode, der die Logik der iterativen binären Suche in Java zeigt :

Implementierung der binären Suche in Java

Hier ist ein Beispielprogramm zum Implementieren der binären Suche in Java. Der Algorithmus wird rekursiv implementiert. Eine interessante Tatsache über die Implementierung der binären Suche in Java ist auch, dass Joshua Bloch, Autor des berühmten Buches Effective Java, die binäre Suche in „java.util.Arrays“ geschrieben hat.

import java.util.Arrays;import java.util.Scanner;
/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/
public class IterativeBinarySearch {
 public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
 binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333);
 // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list);
 // Search an element int index = Arrays.binarySearch(list, 3);
}
/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */
public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;
while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {
System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}
middle = (first + last) / 2;
}
if (first > last) { System.out.println(number + " is not present in the list.\n");}
}
}
OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.

Hier geht es darum, wie die binäre Suche mithilfe der Rekursion in Java implementiert wird . Neben der linearen Suche sind dies zwei der wichtigsten Suchalgorithmen, die Sie in Ihrem Informatikunterricht lernen.

Die Datenstruktur des binären Suchbaums nutzt diesen Algorithmus und ordnet Daten in einer hierarchischen Struktur an, sodass Sie jeden Knoten in O (logN) -Zeit durchsuchen können.

Sie müssen sich jedoch daran erinnern, dass Sie für die Verwendung der binären Suche eine sortierte Liste oder ein sortiertes Array benötigen. Daher müssen Sie auch die Kosten für das Sortieren berücksichtigen, wenn Sie den binären Suchalgorithmus in der realen Welt verwenden möchten.

Weiteres Lernen

Datenstrukturen und Algorithmen: Deep Dive mit Java

Algorithmen und Datenstrukturen - Teil 1 und 2

Datenstrukturen in Java 9 von Heinz Kabutz

10 Algorithmenbücher für Interviews

10 Datenstruktur- und Algorithmuskurse für Interviews

5 kostenlose Kurse zum Erlernen der Datenstruktur und der Algorithmen

Weitere Tutorials zu Datenstruktur und Algorithmen, die Ihnen gefallen könnten

  • Wie implementiere ich den Quicksort-Algorithmus in Java? (Lernprogramm)
  • Wie implementiere ich den binären Suchbaum in Java? (Lösung)
  • Wie implementiere ich den Quicksort-Algorithmus ohne Rekursion? (Lernprogramm)
  • Wie implementiere ich einen Einfügesortieralgorithmus in Java? (Lernprogramm)
  • Wie implementiere ich den Bubble-Sortieralgorithmus in Java? (Lernprogramm)
  • Was ist der Unterschied zwischen einem auf Vergleich und Nichtvergleich basierenden Sortieralgorithmus? (Antworten)
  • Wie implementiere ich Bucket Sort in Java? (Lernprogramm)
  • Wie implementiere ich einen binären Suchalgorithmus ohne Rekursion in Java? (Lernprogramm)
  • 50+ Kurse zu Datenstruktur und Algorithmen für Programmierer (Fragen)

Vielen Dank für das Lesen dieses Artikels. Wenn Ihnen dieser Artikel gefällt, teilen Sie ihn bitte mit Ihren Freunden und Kollegen. Wenn Sie Vorschläge oder Feedback haben, hinterlassen Sie bitte einen Kommentar.

PS - Wenn Sie es ernst meinen, Ihre Algorithmen zu verbessern, sind die Datenstrukturen und Algorithmen: Deep Dive mit Java meiner Meinung nach die beste Lösung.