Bevor wir die Unterschiede zwischen der linearen und der binären Suche verstehen, sollten wir zunächst die lineare Suche und die binäre Suche getrennt kennen.
Was ist eine lineare Suche?
Eine lineare Suche wird auch als sequentielle Suche bezeichnet, bei der einfach jedes Element gleichzeitig gescannt wird. Angenommen, wir möchten ein Element in einem Array oder einer Liste durchsuchen. Wir berechnen einfach seine Länge und springen nicht auf irgendein Element.
Betrachten wir ein einfaches Beispiel.
Angenommen, wir haben ein Array mit 10 Elementen, wie in der folgenden Abbildung dargestellt:
Die obige Abbildung zeigt ein Array vom Typ Zeichen mit 10 Werten. Wenn wir nach „E“ suchen möchten, beginnt die Suche bei 0ThElement und durchsucht jedes Element, bis das Element, d. h. „E“, nicht mehr gefunden wird. Wir können nicht direkt von der 0 springenThElement zur 4ThElement, d. h. jedes Element wird einzeln gescannt, bis das Element nicht mehr gefunden wird.
Komplexität der linearen Suche
Bei der linearen Suche wird jedes Element einzeln durchsucht, bis das Element nicht mehr gefunden wird. Wenn die Anzahl der Elemente zunimmt, erhöht sich auch die Anzahl der zu scannenden Elemente. Wir können sagen, dass die Die zum Durchsuchen der Elemente benötigte Zeit ist proportional zur Anzahl der Elemente . Daher ist die Komplexität im schlimmsten Fall O(n)
Was ist eine binäre Suche?
Eine binäre Suche ist eine Suche, bei der das mittlere Element berechnet wird, um zu prüfen, ob es kleiner oder größer als das zu durchsuchende Element ist. Der Hauptvorteil der binären Suche besteht darin, dass nicht jedes Element in der Liste gescannt wird. Anstatt jedes Element zu scannen, wird die Suche nur in der Hälfte der Liste durchgeführt. Daher benötigt die binäre Suche im Vergleich zu einer linearen Suche weniger Zeit für die Suche nach einem Element.
Der Eine Voraussetzung der binären Suche ist, dass ein Array in sortierter Reihenfolge vorliegen sollte, während die lineare Suche sowohl für sortierte als auch für unsortierte Arrays funktioniert. Der binäre Suchalgorithmus basiert auf der Divide-and-Conquer-Technik, was bedeutet, dass er das Array rekursiv teilt.
Bei der binären Suche werden drei Fälle verwendet:
Fall 1: Daten
Fall 2: Daten>a[Mitte], dann rechts=Mitte-1
Fall 3: data = a[mid] // Element wird gefunden
Im obigen Fall: ' A ' ist der Name des Arrays, Mitte ist der rekursiv berechnete Index des Elements, Daten ist das zu suchende Element, links bezeichnet das linke Element des Arrays und Rechts bezeichnet das Element, das auf der rechten Seite des Arrays auftritt.
Lassen Sie uns die Funktionsweise der binären Suche anhand eines Beispiels verstehen.
Angenommen, wir haben ein Array mit einer Größe von 10, das von 0 bis 9 indiziert ist, wie in der folgenden Abbildung dargestellt:
Wir möchten nach 70 Elementen aus dem obigen Array suchen.
Schritt 1: Zuerst berechnen wir das mittlere Element eines Arrays. Wir betrachten zwei Variablen, nämlich links und rechts. Zunächst ist links = 0 und rechts = 9, wie in der folgenden Abbildung dargestellt:
Der mittlere Elementwert kann wie folgt berechnet werden:
Daher ist mid = 4 und a[mid] = 50. Das zu durchsuchende Element ist 70, daher ist a[mid] nicht gleich data. Der Fall 2 ist erfüllt, d. h. data>a[mid].
Schritt 2: Da data>a[mid] ist, wird der Wert von left um mid+1 erhöht, d. h. left=mid+1. Der Wert von mid ist 4, also wird der Wert von left zu 5. Jetzt haben wir ein Subarray, wie in der folgenden Abbildung gezeigt:
Nun wird der Mittelwert erneut mithilfe der obigen Formel berechnet und der Mittelwert wird zu 7. Nun kann der Mittelwert wie folgt dargestellt werden:
In der obigen Abbildung können wir beobachten, dass a[mid]>data ist, sodass der Wert von mid im nächsten Schritt erneut berechnet wird.
Schritt 3: Als[mid]>data wird der Wert von right um mid-1 dekrementiert. Der Wert von mid ist 7, daher wird der Wert von right zu 6. Das Array kann wie folgt dargestellt werden:
Der Wert von mid wird erneut berechnet. Die Werte für links und rechts sind 5 bzw. 6. Daher beträgt der Wert von „mid“ 5. Jetzt kann „mid“ wie unten gezeigt in einem Array dargestellt werden:
In der obigen Abbildung können wir beobachten, dass a[mid]
Schritt 4: Als[Mitte] Nun wird der Wert von mid erneut anhand der bereits besprochenen Formel berechnet. Die Werte von links und rechts betragen jeweils 6 und 6, sodass der Wert von Mitte zu 6 wird, wie in der folgenden Abbildung dargestellt: In der obigen Abbildung können wir beobachten, dass a[mid]=data. Damit ist die Suche abgeschlossen und das Element wurde erfolgreich gefunden. Im Folgenden sind die Unterschiede zwischen der linearen Suche und der binären Suche aufgeführt: Beschreibung Die lineare Suche ist eine Suche, die ein Element in der Liste findet, indem das Element nacheinander durchsucht wird, bis das Element in der Liste gefunden wird. Andererseits ist eine binäre Suche eine Suche, die das mittlere Element in der Liste rekursiv findet, bis das mittlere Element mit einem gesuchten Element übereinstimmt. Funktionieren beider Suchvorgänge Die lineare Suche beginnt mit der Suche beim ersten Element und scannt jeweils ein Element, ohne zum nächsten Element zu springen. Andererseits teilt die binäre Suche das Array in zwei Hälften, indem das mittlere Element eines Arrays berechnet wird. Implementierung Die lineare Suche kann für jede lineare Datenstruktur wie Vektoren, einfach verknüpfte Listen und doppelt verknüpfte Listen implementiert werden. Im Gegensatz dazu kann die binäre Suche auf Datenstrukturen mit bidirektionaler Durchquerung, d. h. Vorwärts- und Rückwärtsdurchquerung, implementiert werden. Komplexität Die lineare Suche ist einfach zu verwenden, oder wir können sagen, dass sie weniger komplex ist, da die Elemente für eine lineare Suche in beliebiger Reihenfolge angeordnet werden können, während bei einer binären Suche die Elemente in einer bestimmten Reihenfolge angeordnet werden müssen. Sortierte Elemente Die Elemente für eine lineare Suche können in zufälliger Reihenfolge angeordnet werden. Bei der linearen Suche ist es nicht zwingend erforderlich, dass die Elemente in einer sortierten Reihenfolge angeordnet sind. Bei einer binären Suche hingegen müssen die Elemente in sortierter Reihenfolge angeordnet werden. Es kann entweder in aufsteigender oder absteigender Reihenfolge angeordnet werden, und dementsprechend wird der Algorithmus geändert. Da bei der binären Suche ein sortiertes Array verwendet wird, ist es notwendig, das Element an der richtigen Stelle einzufügen. Im Gegensatz dazu benötigt die lineare Suche kein sortiertes Array, sodass das neue Element einfach am Ende des Arrays eingefügt werden kann. Ansatz Die lineare Suche verwendet einen iterativen Ansatz zum Auffinden des Elements und wird daher auch als sequenzieller Ansatz bezeichnet. Im Gegensatz dazu berechnet die binäre Suche das mittlere Element des Arrays und verwendet daher den Divide-and-Conquer-Ansatz. Datensatz Die lineare Suche ist für große Datensätze nicht geeignet. Wenn wir das Element durchsuchen möchten, das das letzte Element des Arrays ist, beginnt eine lineare Suche mit der Suche beim ersten Element und geht bis zum letzten Element weiter, sodass die Suche nach dem Element viel Zeit in Anspruch nehmen würde. Andererseits eignet sich die binäre Suche für einen großen Datensatz, da sie weniger Zeit in Anspruch nimmt. Geschwindigkeit Wenn der Datensatz bei der linearen Suche groß ist, ist der Rechenaufwand hoch und die Geschwindigkeit wird langsamer. Wenn der Datensatz bei der binären Suche groß ist, ist der Rechenaufwand im Vergleich zu einer linearen Suche geringer und die Geschwindigkeit steigt. Maße Die lineare Suche kann sowohl für eindimensionale als auch für mehrdimensionale Arrays verwendet werden, während die binäre Suche nur für eindimensionale Arrays implementiert werden kann. Effizienz Die lineare Suche ist weniger effizient, wenn wir große Datenmengen berücksichtigen. Bei großen Datenmengen ist die binäre Suche effizienter als die lineare Suche. Schauen wir uns die Unterschiede in tabellarischer Form an. 
Unterschiede zwischen linearer Suche und binärer Suche
Python-Konstruktor
Vergleichsbasis Lineare Suche Binäre Suche Definition Die lineare Suche beginnt mit der Suche beim ersten Element und vergleicht jedes Element mit einem gesuchten Element, bis das Element nicht gefunden wird. Es ermittelt die Position des gesuchten Elements, indem es das mittlere Element des Arrays findet. Sortierte Daten Bei einer linearen Suche müssen die Elemente nicht in sortierter Reihenfolge angeordnet werden. Voraussetzung für die binäre Suche ist, dass die Elemente in einer sortierten Reihenfolge angeordnet sind. Implementierung Die lineare Suche kann für jede lineare Datenstruktur wie ein Array, eine verknüpfte Liste usw. implementiert werden. Die Implementierung der binären Suche ist begrenzt, da sie nur für Datenstrukturen implementiert werden kann, die eine bidirektionale Durchquerung ermöglichen. Ansatz Es basiert auf dem sequenziellen Ansatz. Es basiert auf dem Divide-and-Conquer-Ansatz. Größe Dies ist für kleine Datensätze vorzuziehen. Dies ist für große Datensätze vorzuziehen. Effizienz Bei großen Datensätzen ist die Effizienz geringer. Bei großen Datensätzen ist dies effizienter. Worst-Case-Szenario Bei einer linearen Suche ist O(n) das schlechteste Szenario für das Auffinden des Elements. Bei einer binären Suche ist das Worst-Case-Szenario zum Auffinden des Elements O(log2N). Best-Case-Szenario Bei einer linearen Suche ist das beste Szenario zum Auffinden des ersten Elements in der Liste O(1). Bei einer binären Suche ist das beste Szenario zum Auffinden des ersten Elements in der Liste O(1). Dimensionsarray Es kann sowohl auf einem ein- als auch auf einem mehrdimensionalen Array implementiert werden. Es kann nur auf einem mehrdimensionalen Array implementiert werden.