Binärer Suchalgorithmus: Funktion, Vorteile, Zeit- und Raumkomplexität

Einführung

In jedem Computersystem ist die Suche eine der kritischsten zu entwickelnden Funktionalitäten. Suchtechniken werden beim Abrufen von Dateien, Indizieren und vielen anderen Anwendungen verwendet. Es stehen viele Suchtechniken zur Verfügung. Eine davon ist die binäre Suchtechnik.

Ein binärer Suchalgorithmus arbeitet mit der Idee, bei jeder Iteration die Hälfte der Liste zu vernachlässigen. Es teilt die Liste weiter auf, bis es den gesuchten Wert in einer gegebenen Liste findet. Ein binärer Suchalgorithmus ist ein schnelles Upgrade auf einen einfachen linearen Suchalgorithmus.

Keine Programmiererfahrung erforderlich. 360° Karriereunterstützung. PG-Diplom in maschinellem Lernen und KI von IIIT-B und upGrad.

Funktionsweise eines binären Suchalgorithmus

Das erste, was zu beachten ist, ist, dass ein binärer Suchalgorithmus immer auf einer sortierten Liste arbeitet. Daher ist der erste logische Schritt, die bereitgestellte Liste zu sortieren. Nach dem Sortieren wird der Median der Liste mit dem gewünschten Wert überprüft.

• Wenn der gewünschte Wert gleich dem Wert des zentralen Index ist, wird der Index als Antwort zurückgegeben.

• Wenn der Zielwert niedriger ist als der Deal des zentralen Indexes der Liste, dann wird die rechte Seite der Liste ignoriert.

• Wenn der gewünschte Wert größer als der Wert des zentralen Index ist, wird die linke Hälfte verworfen.

• Der Vorgang wird dann für verkürzte Listen wiederholt, bis der Zielwert gefunden ist.

Beispiel 1

Betrachten wir den Algorithmus anhand eines Beispiels. Angenommen, es gibt eine Liste mit den folgenden Nummern:

1, 15, 23, 7, 6, 14, 8, 3, 27

Nehmen wir den gewünschten Wert als 27 an. Die Gesamtzahl der Elemente in der Liste beträgt 9.

Der erste Schritt besteht darin, die Liste zu sortieren. Nach dem Sortieren würde die Liste in etwa so aussehen:

1, 3, 6, 7, 8, 14, 15, 23, 27

Da die Anzahl der Elemente in der Liste neun ist, wäre der zentrale Index bei fünf. Der Wert bei Index fünf ist 8. Der gewünschte Wert 27 wird mit dem Wert 8 verglichen. Prüfen Sie zunächst, ob der Wert gleich 8 ist oder nicht. Wenn ja, Index zurückgeben und beenden.

Da 27 größer als 8 ist, würden wir den linken Teil ignorieren und nur die rechte Seite der Liste durchlaufen. Die neue zu durchlaufende Liste lautet:

14, 15, 23, 27

Hinweis: In der Praxis wird die Liste nicht abgeschnitten. Nur die Beobachtung wird eingeengt. Die „neue Liste“ sollte also nicht mit dem Erstellen einer neuen Liste oder dem Kürzen der ursprünglichen Liste verwechselt werden. Obwohl es mit einer neuen Liste implementiert werden könnte, gibt es zwei Probleme. Erstens wird es einen Speicher-Overhead geben. Jede neue Liste erhöht die Platzkomplexität. Und zweitens müssen die ursprünglichen Indizes bei jeder Iteration nachverfolgt werden.

Der neue zentrale Index kann je nach Implementierung als zweites oder drittes Element verwendet werden. Hier betrachten wir das dritte Element als zentral. Der Wert 23 wird mit dem Wert 27 verglichen. Da der Wert größer als der mittlere Wert ist, verwerfen wir die linke Hälfte.

Die zu durchlaufende Liste lautet:

27

Da die Liste nur ein einziges Element enthält, wird dieses als zentrales Element betrachtet. Daher vergleichen wir den gewünschten Wert mit 27. Wenn sie übereinstimmen, geben wir den Indexwert von 27 in der ursprünglichen Liste zurück.

Beispiel #2

Nehmen wir in derselben Liste an, dass der gewünschte Wert 2 ist.

Zuerst wird der zentrale Wert acht mit 2 verglichen. Da der gewünschte Wert kleiner als der zentrale Wert ist, verengen wir unseren Fokus auf die linke Seite der Liste.

Die neue Traversierung besteht aus:

1, 3, 6, 7

Nehmen wir als zweites Element das zentrale Element. Der gewünschte Wert Zwei wird mit 3 verglichen. Da der Wert noch kleiner ist, grenzen wir den Fokus wieder auf die linke Seite der Liste ein.

Die neue Traversierung besteht aus:

1

Da die Verfahrliste nur ein Element hat, wird der Wert direkt mit dem restlichen Element verglichen. Wir sehen, dass die Werte nicht übereinstimmen. Daher brechen wir mit einer Fehlermeldung aus der Schleife aus: Wert nicht gefunden .

Data Science Advanced-Zertifizierung, über 250 Einstellungspartner, über 300 Lernstunden, 0 % EMI

Zeit- und Raumkomplexität

Die Zeitkomplexität des binären Suchalgorithmus ist O(log n). Die Zeitkomplexität im besten Fall wäre O(1), wenn der zentrale Index direkt mit dem gewünschten Wert übereinstimmen würde. Das Worst-Case-Szenario könnten die Werte an beiden Enden der Liste oder Werte sein, die nicht in der Liste enthalten sind.

Die Raumkomplexität des binären Suchalgorithmus hängt von der Implementierung des Algorithmus ab. Es gibt zwei Möglichkeiten, es zu implementieren:

1. Iterative Methode
2. Rekursive Methode

Beide Methoden sind ziemlich gleich, mit zwei Unterschieden in der Implementierung. Erstens gibt es bei der rekursiven Methode keine Schleife. Zweitens übergibt er die neuen Werte nicht an die nächste Iteration der Schleife, sondern an die nächste Rekursion. Beim iterativen Verfahren können die Iterationen durch die Schleifenbedingungen gesteuert werden, während beim rekursiven Verfahren Maximum und Minimum als Randbedingung verwendet werden.

Beim iterativen Verfahren wäre die Raumkomplexität O(1). Bei der rekursiven Methode wäre die Raumkomplexität O(log n).

Leistungen

• Ein binärer Suchalgorithmus ist ein ziemlich einfach zu implementierender Suchalgorithmus.

• Es ist eine deutliche Verbesserung gegenüber der linearen Suche und bietet im Vergleich zu einigen der schwieriger zu implementierenden Suchalgorithmen fast die gleiche Leistung.

• Der binäre Suchalgorithmus zerlegt die Liste bei jeder Iteration in zwei Hälften, anstatt die Liste sequentiell zu durchkämmen. Bei großen Listen kann diese Methode sehr nützlich sein.

Checkout: Entscheidungsbaum-Klassifizierung: Alles, was Sie wissen müssen

Fazit

Ein binärer Suchalgorithmus ist ein weit verbreiteter Algorithmus im Computerbereich. Es ist ein fetter und genauer Suchalgorithmus, der sowohl bei großen als auch bei kleinen Datensätzen gut funktionieren kann. Ein binärer Suchalgorithmus ist ein einfach und zuverlässig zu implementierender Algorithmus. Bei der Zeit- und Raumanalyse sind die Vorteile der Verwendung dieser speziellen Technik offensichtlich.

Wenn Sie neugierig sind, mehr über Data Science zu erfahren, schauen Sie sich das PG Diploma in Data Science von IIIT-B & upGrad an, das für Berufstätige entwickelt wurde und mehr als 10 Fallstudien und Projekte, praktische Workshops, Mentoring mit Branchenexperten, 1- on-1 mit Mentoren aus der Branche, mehr als 400 Stunden Lern- und Jobunterstützung bei Top-Unternehmen.