Was ist binäre Suche?

Eine binäre Suche ist ein Suchalgorithmus, mit dem Zielelemente in einem Container gesucht werden, in dem Elemente in aufsteigender Reihenfolge angeordnet werden müssen. Im Allgemeinen wird die binäre Suche verwendet, um die Indexnummer des Zielelements in einem sortierten Array durchzuführen.

Die binäre Suche verwendet den Ansatz der Kluft und erobert, bei dem das Array in gleiche Teile unterteilt wird, bis es das Zielelement findet.

Ein binärer Suchalgorithmus wird sowohl iterativ als auch eine rekursive Aussage implementiert. Die binäre Suche ist effizienter und schneller als die lineare Suche.

Binärer Suchalgorithmus

1. Sortieren und arrangieren Sie die Elemente im Array arr in aufsteigender Reihenfolge.
2. Die Algorithmen vergleichen das mittlere Element N mit dem Zielelement Ziel.
3. Der Algorithmus gibt den Positionsindex des mittleren Elements zurück, wenn festgestellt wird, dass das Zielelement gleich dem mittleren Element ist,
4. Der Algorithmus durchsucht die untere Hälfte des Arrays, wenn das Zielelement geringer ist als das mittlere Element.
5. Der Algorithmus durchsucht die obere Hälfte des Arrays, wenn das Zielelement größer ist als das mittlere Element.
6. Der Algorithmus wiederholt immer wieder die 4. und 5. Schritte, bis die Länge des Arrays eins oder weniger als 1 wird.

Am Ende wird entweder der Indexwert des Elements zurückgegeben, oder das Element gibt es im Array nicht.

Binär -Suche Pseudocode

Iterativ

Funktion binary_search (arr, n, target) ist
links: = 0
Rechte: = n - 1
während links ≤ rechts tun
Mitte: = Boden ((links + rechts) / 2)
Wenn arr [Middle] Ziel dann
Rechts: = Mitte - 1
anders:
Mitte zurückkehren
Kehren Sie erfolglos zurück

Rekursiv

Funktion binary_search (arr, links, rechts, Ziel) ist
Wenn rechts> = links
Mitte = (links+rechts) // 2
Wenn arr [Middle] == Ziel
Mitte zurückkehren
sonst wenn arr [Mitte]> Tarrget
Return Binary_search (arr, niedrig, Mid-1, Ziel)
anders
zurückbinary_search zurückgeben (arr, Mid+1, rechts, Ziel)
anders
Kehren Sie erfolglos zurück

Implementieren Sie die binäre Suche in Python

Iterativ
Im iterativen Ansatz verwenden wir die Schleifen, um binäre Suche zu implementieren.

Def Binary_search (arr, n, Ziel):
links = 0
rechts = n-1
Mitte = 0
während links<=right:
Mitte = (rechts+links) // 2
#Wenn das mittlere Element dem Zielelement gleich ist
Wenn arr [Middle] == Ziel:
Mitte zurückkehren
# Wenn das Zielelement größer ist als das mittlere Element
elif arr [Mitte]< target:
links = Mitte+1
# Wenn das Zielelement weniger als das mittlere Element ist
anders:
Right = Middle-1
# Wenn das Zielelement im Array nicht vorhanden ist
Rückkehr -1
Wenn __name__ == '__main__':
# sortiertes Array
Sorted_arr = [0,4,7,10,14,23,45,47,53]
# Länge des Arrays
n = len (sorted_arr)
#LEILement zu suchen
Ziel = 47
Position = Binary_search (Sorted_arr, n, Ziel)
Wenn Position != -1:
print (f "element target vorhanden am Index Position")
anders:
print (f "element target ist in Array nicht vorhanden")

Ausgang

Element 47 in Index 7 vorhanden

Rekursiv
In rekursiver, anstatt die Schleife zu verwenden, rufen wir die Funktion immer wieder auf, bis die Basisbedingung erfüllt wird

Def Binary_search (arr, links, rechts, Ziel):
#Base -Bedingung
Wenn rechts:
Return Binary_search (arr, links, Mitte-1, Ziel)
#Wenn das Zielelement kleiner ist als das mittlere Element
anders:
Return Binary_Search zurück (arr, Mitte+1, rechts, Ziel)
Wenn __name__ == '__main__':
# sortiertes Array
Sorted_arr = [0,4,7,10,14,23,45,47,53]
links = 0
Right = len (sorted_arr) -1
#LEILement zu suchen
Ziel = 47
Position = Binary_search (sorted_arr, links, rechts, Ziel)
Wenn Position != -1:
print (f "element target vorhanden am Index Position")
anders:
print (f "element target ist in Array nicht vorhanden")

Ausgang

Element 90 ist im Array nicht vorhanden

Komplexität

Binäre Suche hat eine zeitliche Komplexität von O (log n), wo N ist die Anzahl der im Array vorhandenen Elemente.

Die binäre Suche hat eine Raumkomplexität von O (1), da wir im Algorithmus die In-Place-Suche durchführen.

Abschluss

Binäre Suche ist eine der besten und effizienten Suchalgorithmen. Die Zeit und die Raumkomplexität der binären Suche sind ebenfalls sehr niedrig. Die einzige Voraussetzung für die binäre Suche ist, dass das Eingangsarray in aufsteigender Reihenfolge sortiert werden sollte.