Einer der grundlegendsten Algorithmen in der Informatik ist der binäre Suchalgorithmus. Sie können die binäre Suche mit zwei Methoden implementieren: der iterativen Methode und der rekursiven Methode. Während beide Verfahren die gleiche Zeitkomplexität aufweisen, ist das iterative Verfahren in Bezug auf die Raumkomplexität viel effizienter.

Das iterative Verfahren hat eine Raumkomplexität von O(1) verglichen mit O(logn) nach dem rekursiven Verfahren erstellt. Wie können Sie also den binären Suchalgorithmus mithilfe der iterativen Methode in C, C++ und Python implementieren?

Was ist binäre Suche?

Die binäre Suche, auch bekannt als Halbintervallsuche, logarithmische Suche oder binäres Hacken, ist ein Algorithmus, der die Position eines Elements in einem sortierten Array sucht und zurückgibt. Das Suchelement wird mit dem mittleren Element verglichen. Wenn Sie den Durchschnitt der unteren und oberen Grenze nehmen, können Sie die mittleren Elemente finden.

Wenn das Suchelement größer als das mittlere Element ist, bedeutet dies, dass alle Elemente auf der linken Seite kleiner als das Suchelement sind. Das Steuerelement verschiebt sich also auf die rechte Seite des Arrays (wenn das Array in aufsteigender Reihenfolge ist), indem die untere Grenze auf die nächste Position des mittleren Elements erhöht wird.

instagram viewer

Wenn das Suchelement kleiner als das mittlere Element ist, bedeutet dies gleichermaßen, dass alle Elemente auf der rechten Seite größer als das Suchelement sind. Das Steuerelement verschiebt sich also in den linken Teil des Arrays, indem die Obergrenze auf die vorherige Position des mittleren Elements geändert wird.

Dies reduziert die Anzahl der Vergleiche drastisch im Vergleich zu Implementierung der linearen Suche wobei dort die Anzahl der Vergleiche gleich der Anzahl der Elemente im Worst-Case-Szenario ist. Diese Methode erweist sich als sehr nützlich, um Nummern in einem Telefonbuch oder Wörter in einem Wörterbuch zu finden.

Hier ist eine schematische Darstellung der Binärer Suchalgorithmus:

Binäre Suche mit C

Befolgen Sie diese Schritte, um die binäre Suche mit C zu implementieren:

Darin ist der gesamte Quellcode des binären Suchprogramms mit C, C++, Java und Python vorhanden GitHub-Repository.

Das Programm definiert eine Funktion, binäre Suche(), die entweder den Index des gefundenen Werts oder zurückgibt -1 falls nicht vorhanden:

#enthalten <stdio.h>
intbinäre Suche(int arr[], int arr_size, int Suchnummer){
/*... */
}

Die Funktion arbeitet, indem sie den Suchraum iterativ eingrenzt. Da die binäre Suche auf sortierten Arrays funktioniert, können Sie die Mitte berechnen, was sonst keinen Sinn ergibt. Sie können den Benutzer entweder nach einem sortierten Array fragen oder Sortieralgorithmen wie Bubble oder Selection Sort verwenden.

Der niedrig Und hoch Variablen speichern die Indizes, die die Grenzen des aktuellen Suchraums darstellen. Mitte speichert den Index in der Mitte:

int niedrig = 0, hoch = arr_size - 1, Mitte;

Die wichtigsten während() Schleife grenzt den Suchraum ein. Wenn der Wert des niedrigen Index jemals größer wird als der hohe Index, dann ist der Suchraum erschöpft, sodass der Wert nicht vorhanden sein kann.

während (niedrig <= hoch) {
/* geht weiter... [1] */
 }
zurückkehren-1;

Nach dem Aktualisieren des Mittelpunkts am Anfang der Schleife gibt es drei mögliche Ergebnisse:

  1. Wenn der Wert am Mittelpunkt der gesuchte ist, geben Sie diesen Index zurück.
  2. Wenn der Mittelpunktwert größer als der gesuchte Wert ist, reduzieren Sie das Hoch.
  3. Wenn der Mittelpunktwert niedriger ist, erhöhen Sie das Tief. 
/* [1] ...Fortsetzung */
 mittel = (niedrig + (hoch - niedrig)) / 2;
if (arr[mid] == Suchnummer)
zurückkehren Mitte;
andersWenn (arr[mid] > search_number)
 hoch = mittel - 1;
anders
 niedrig = mittel + 1;

Testen Sie die Funktion mit Benutzereingaben. Verwenden scanf() um Eingaben von der Befehlszeile zu erhalten, einschließlich der Array-Größe, seines Inhalts und einer Zahl, nach der gesucht werden soll:

inthauptsächlich(){
int arr[100], i, arr_size, search_number;
 printf("Anzahl der Elemente eingeben: ");
 scanf("%D", &arr_size);
 printf("Bitte Zahlen eingeben: ");
für (i = 0; ich < arr_size; i++) {
 scanf("%D", &arr[i]);
 }


printf("Geben Sie die zu suchende Nummer ein: ");
 scanf("%D", &Suchnummer);


i = binarySearch (arr, arr_size, search_number);


wenn (i==-1)
 printf("Nummer nicht vorhanden");
anders
 printf("Nummer ist an Position %d vorhanden", i + 1);
zurückkehren0;
}

Wenn Sie die Nummer finden, zeigen Sie ihre Position oder ihren Index an, andernfalls wird keine Meldung angezeigt, dass die Nummer vorhanden ist.

Binäre Suche mit C++

Sie können das C-Programm in ein C++-Programm konvertieren, indem Sie die Eingabe-Ausgabe-Stream Und Namensraum std verwenden um eine mehrfache Wiederholung während des gesamten Programms zu vermeiden.

#enthalten <iostream>
verwenden NamensraumStandard;

Verwenden cout mit Extraktionsoperator << anstatt printf() Und cin mit Einfügeoperator >> anstatt scanf() und Ihr C++-Programm ist fertig.

printf("Anzahl der Elemente eingeben: ");
cout <<"Anzahl der Elemente eingeben: ";
scanf("%D", &arr_size);
cin >> arr_size;

Binäre Suche mit Python

Da Python keine eingebaute Unterstützung für Arrays hat, verwenden Sie Listen. Funktion definieren, binäre Suche(), das drei Parameter akzeptiert, die Liste, ihre Größe und eine Zahl, nach der gesucht werden soll:

defbinäre Suche(arr, arr_size, search_number):
 niedrig = 0
 hoch = arr_size - 1
während niedrig <= hoch:
 mittel = tief + (hoch-tief)//2
 if arr[mid] == search_number:
zurückkehren Mitte
elf arr[mid] > Suchnummer:
 hoch = mittel - 1
anders:
 niedrig = mittel + 1
zurückkehren-1

Initialisieren Sie zwei Variablen, niedrig Und hoch, um als Unter- und Obergrenze der Liste zu dienen. Verwenden Sie ähnlich wie bei der C-Implementierung a während Schleife, die den Suchraum eingrenzt. Initialisieren Mitte um den mittleren Wert der Liste zu speichern. Python bietet den Floor-Division-Operator (//), der die größtmögliche ganze Zahl liefert.

Führen Sie die Vergleiche durch und grenzen Sie den Suchraum ein, bis der Mittelwert gleich der Suchzahl ist. Wenn die Suchnummer nicht vorhanden ist, kehrt die Steuerung zurück -1.

arr_size = int (eingabe("Anzahl der Elemente eingeben: "))
arr=[]
drucken("Bitte Zahlen eingeben: ", Ende="")
für i im Bereich (0,arr_size):
 arr.append(int(Eingang()))
Suchnummer = int (Eingabe ("Geben Sie die zu suchende Nummer ein: "))
result = binarySearch (arr, arr_size, search_number)
wenn Ergebnis == -1:
 drucken("Nummer nicht vorhanden")
anders:
 print("Nummer Ist vorhanden an Position ", (Ergebnis + 1))

Testen Sie die Funktion mit Benutzereingaben. Verwenden Eingang() um die Listengröße, ihren Inhalt und eine zu suchende Nummer zu erhalten. Verwenden int() um die von Python standardmäßig akzeptierte Zeichenfolgeneingabe in eine Ganzzahl umzuwandeln. Um Nummern zur Liste hinzuzufügen, verwenden Sie die anhängen () Funktion.

Forderung binäre Suche() und übergeben Sie die Argumente. Wenn Sie die Nummer finden, zeigen Sie ihre Position oder ihren Index an, andernfalls wird keine Meldung angezeigt, dass die Nummer vorhanden ist.

Ausgabe des binären Suchalgorithmus

Das Folgende ist die Ausgabe des binären Suchalgorithmus, wenn das Element im Array vorhanden ist:

Das Folgende ist die Ausgabe des binären Suchalgorithmus, wenn das Element nicht im Array vorhanden ist:

Lernen Sie die grundlegenden Datenstrukturen und Algorithmen

Die Suche ist einer der ersten Algorithmen, die Sie lernen, und wird oft in Programmierwettbewerben, Platzierungen und Vorstellungsgesprächen gefragt. Einige andere Algorithmen, die Sie lernen sollten, sind Sortier-, Hash-, dynamische Programmierungs-, String-Matching- und Primzahl-Testalgorithmen.

Darüber hinaus ist es wichtig, die zeitliche und räumliche Komplexität von Algorithmen zu verstehen. Sie sind eines der wichtigsten Konzepte in der Informatik bei der Bestimmung der Effizienz eines Algorithmus. Mit Kenntnissen über Datenstrukturen und Algorithmen werden Sie bestimmt die besten Programme erstellen.