So implementieren Sie die binäre Suche mithilfe der iterativen Methode
Der binäre Suchalgorithmus folgt dem Divide-and-Conquer-Paradigma. Erfahren Sie, wie Sie mit der platzsparenden Methode nach Elementen in einem sortierten Array suchen.
Einer der grundlegendsten Algorithmen 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 Methoden die gleiche zeitliche Komplexität aufweisen, ist die iterative Methode hinsichtlich der räumlichen Komplexität deutlich effizienter.
Die iterative Methode hat eine Raumkomplexität von O(1) im Vergleich zu O(logn), die durch die rekursive Methode erzeugt wird. 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är-Chop, 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 Grenzen bilden, können Sie die mittleren Elemente ermitteln.
Wenn das Suchelement größer als das mittlere Element ist, bedeutet dies, dass alle Elemente auf der linken Seite kleiner als das Suchelement sind. Die Steuerung verschiebt sich also auf die rechte Seite des Arrays (wenn das Array in aufsteigender Reihenfolge vorliegt), indem die Untergrenze auf die nächste Position des mittleren Elements erhöht wird.
Wenn das Suchelement kleiner als das mittlere Element ist, bedeutet dies ebenfalls, dass alle Elemente auf der rechten Seite größer als das Suchelement sind. Die Steuerung 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 zur linearen Suchimplementierung, bei der die Anzahl der Vergleiche der Anzahl der Elemente im schlimmsten Fall entspricht. 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 des binären Suchalgorithmus:
Binäre Suche mit C
Befolgen Sie diese Schritte, um die binäre Suche mit C zu implementieren:
Der gesamte Quellcode des Binary Search Program mit C, C++, Java und Python ist in diesem GitHub-Repository vorhanden.
Das Programm definiert eine Funktion, binarySearch(), die entweder den Index des gefundenen Werts oder -1 zurückgibt, wenn dieser nicht vorhanden ist:
#include <stdio.h>
int binarySearch(int arr[], int arr_size, int search_number) {
/* ... */
}
Die Funktion funktioniert durch iteratives Eingrenzen des Suchraums. Da die binäre Suche bei 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 Blasen- oder Auswahlsortierung verwenden.
Die Variablen low und high speichern die Indizes, die die Grenzen des aktuellen Suchraums darstellen. mid speichert den Index in der Mitte:
int low = 0, high = arr_size - 1, mid;
Die Hauptschleife while() schränkt den Suchraum ein. Wenn der Wert des niedrigen Index jemals größer als der hohe Index wird, ist der Suchraum erschöpft und der Wert kann nicht vorhanden sein.
while (low <= high) {
/* continues... [1] */
}
return -1;
Nach der Aktualisierung des Mittelpunkts am Anfang der Schleife gibt es drei mögliche Ergebnisse:
- Wenn der Wert in der Mitte der gesuchte Wert ist, geben Sie diesen Index zurück.
- Wenn der Mittelpunktwert größer als der gesuchte Wert ist, verringern Sie den Höchstwert.
- Wenn der Mittelwert niedriger ist, erhöhen Sie den Tiefstwert.
/* [1] ...continued */
mid = (low + (high - low)) / 2;
if (arr[mid] == search_number)
return mid;
else if (arr[mid] > search_number)
high = mid - 1;
else
low = mid + 1;
Testen Sie die Funktion mit Benutzereingaben. Verwenden Sie scanf(), um Eingaben von der Befehlszeile abzurufen, einschließlich der Array-Größe, seines Inhalts und einer Zahl, nach der gesucht werden soll:
int main() {
int arr[100], i, arr_size, search_number;
printf("Enter number of elements: ");
scanf("%d", &arr_size);
printf("Please enter numbers: ");
for (i = 0; i < arr_size; i++) {
scanf("%d", &arr[i]);
}
printf("Enter number to be searched: ");
scanf("%d", &search_number);
i = binarySearch(arr, arr_size, search_number);
if (i==-1)
printf("Number not present");
else
printf("Number is present at position %d", i + 1);
return 0;
}
Wenn Sie die Nummer finden, zeigen Sie deren Position oder Index an. Andernfalls wird eine Meldung angezeigt, dass die Nummer nicht vorhanden ist.
Binäre Suche mit C++
Sie können das C-Programm in ein C++-Programm konvertieren, indem Sie den Input Output Stream importieren und den Namespace std verwenden, um eine mehrfache Wiederholung im gesamten Programm zu vermeiden.
#include <iostream>
using namespace std;
Verwenden Sie cout mit dem Extraktionsoperator << anstelle von printf() und cin mit dem Einfügungsoperator >> anstelle von scanf() und Ihr C++-Programm ist fertig.
printf("Enter number of elements: ");
cout << "Enter number of elements: ";
scanf("%d", &arr_size);
cin >> arr_size;
Binäre Suche mit Python
Da Python keine integrierte Unterstützung für Arrays bietet, verwenden Sie Listen. Definieren Sie eine Funktion, binarySearch(), die drei Parameter akzeptiert, die Liste, ihre Größe und eine Zahl, nach der gesucht werden soll:
def binarySearch(arr, arr_size, search_number):
low = 0
high = arr_size - 1
while low <= high:
mid = low + (high-low)//2
if arr[mid] == search_number:
return mid
elif arr[mid] > search_number:
high = mid - 1
else:
low = mid + 1
return -1
Initialisieren Sie zwei Variablen, low und high, die als untere und obere Grenze der Liste dienen. Verwenden Sie ähnlich wie bei der C-Implementierung eine while-Schleife, die den Suchraum einschränkt. Initialisieren Sie mid, um den mittleren Wert der Liste zu speichern. Python stellt den Etagendivisionsoperator (//) bereit, der die größtmögliche Ganzzahl liefert.
Führen Sie die Vergleiche durch und grenzen Sie den Suchraum ein, bis der Mittelwert der Suchzahl entspricht. Wenn die Suchnummer nicht vorhanden ist, gibt die Steuerung -1 zurück.
arr_size = int(input("Enter number of elements: "))
arr=[]
print("Please enter numbers: ", end=" ")
for i in range(0,arr_size):
arr.append(int(input()))
search_number = int(input("Enter number to be searched: "))
result = binarySearch(arr, arr_size, search_number)
if result == -1:
print("Number not present")
else:
print("Number is present at position ", (result + 1))
Testen Sie die Funktion mit Benutzereingaben. Verwenden Sie input() , um die Listengröße, ihren Inhalt und eine zu suchende Zahl abzurufen. Verwenden Sie int(), um die von Python als Standard akzeptierte Zeichenfolgeneingabe in eine Ganzzahl umzuwandeln. Um Zahlen zur Liste hinzuzufügen, verwenden Sie die Funktion append().
Rufen Sie binarySearch() auf und übergeben Sie die Argumente. Wenn Sie die Nummer finden, zeigen Sie deren Position oder Index an. Andernfalls wird eine Meldung angezeigt, dass die Nummer nicht 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 kennen
Das Suchen ist einer der ersten Algorithmen, die Sie erlernen, und wird häufig in Codierungswettbewerben, Praktika und Vorstellungsgesprächen gefragt. Einige andere Algorithmen, die Sie lernen sollten, sind Sortier-, Hashing-, dynamische Programmierungs-, String-Matching- und Primzahltest-Algorithmen.
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 zur Bestimmung der Effizienz eines Algorithmus. Mit Kenntnissen über Datenstrukturen und Algorithmen können Sie mit Sicherheit die besten Programme erstellen.