Was ist der Unterschied zwischen linearer Suche und binärer Suche?

Question

Was ist der Unterschied zwischen linearer Suche und binärer Suche?

Answer 1

Ein linear search schaut eine Liste nach unten, ein Element nach dem anderen, ohne zu springen. Bei der Komplexität handelt es sich um eine O(n) Suche - die Zeit, die für die Suche in der Liste benötigt wird, wird mit der gleichen Geschwindigkeit größer wie die Liste.

Eine binary search ist, wenn Sie mit der Mitte einer sortierten Liste beginnen, und sehen, ob das größer oder kleiner als der Wert ist, den Sie suchen, der bestimmt, ob der Wert in der ersten oder zweiten Hälfte der Liste ist . Springe zum halben Weg durch die Unterliste und vergleiche es wieder. Das ist ungefähr so, wie Menschen typischerweise ein Wort in einem Wörterbuch nachschlagen (obwohl wir bessere Heuristiken verwenden, offensichtlich - wenn du nach "Katze" suchst, tust du das nicht Beginnen Sie bei "M"). In Komplexitätsbegriffen ist dies eine O(log n) Suche - die Anzahl der Suchoperationen wächst langsamer als die Liste, weil Sie den "Suchraum" bei jeder Operation halbieren.

Angenommen, Sie suchen nach U in einer A-Z-Liste von Buchstaben (Index 0-25; wir suchen nach dem Wert bei Index 20).

Eine lineare Suche würde fragen:

list[0] == 'U'? Nr.
list[1] == 'U'? Nr.
list[2] == 'U'? Nr.
list[3] == 'U'? Nr.
list[4] == 'U'? Nr.
list[5] == 'U'?
... list[20] == 'U'? Ja. Fertig.

Die binäre Suche würde fragen:

Vergleichen list[12] ('M') mit 'U': Kleiner, weiter suchen. (Bereich = 13-25)
Vergleichen Sie list[19] ('T') mit 'U': Kleiner, schauen Sie weiter. (Bereich = 20-25)
Vergleichen list[22] ('W') mit 'U': Größer, schau früher. (Bereich = 20-21)
Vergleichen list[20] ('U') mit 'U': Es gefunden! Fertig.

Vergleicht man die beiden:

• Binary Suche erfordert die Eingabedaten sortiert werden; lineare Suche nicht
• Binäre Suche erfordert Bestellung Vergleich; lineare Suche erfordert nur Gleichheitsvergleiche
• Binäre Suche hat Komplexität O (log n); die lineare Suche hat die Komplexität O (n), wie zuvor diskutiert
• Binärsuche erfordert einen wahlfreien Zugriff auf die Daten; lineare Suche erfordert nur sequentiellen Zugriff (dies kann sehr wichtig sein - es bedeutet eine lineare Suche kann Strom Daten beliebiger Größe)

Answer 2

Betrachten Sie es als zwei verschiedene Arten von Ihrem Weg in einem Telefonbuch zu finden.Eine lineare Suche beginnt am Anfang und liest jeden Namen, bis Sie finden, was Sie suchen. Eine binäre Suche hingegen ist, wenn Sie das Buch öffnen (normalerweise in der Mitte), schauen Sie sich den Namen oben auf der Seite an und entscheiden Sie, ob der gesuchte Name größer oder kleiner als der von Ihnen gesuchte ist Ich suche nach. Wenn der gesuchte Name größer ist, dann suchst du den oberen Teil des Buches auf diese Weise weiter.

Answer 3

Eine lineare Suche beginnt am Anfang einer Liste von Werten und prüft 1 nach 1, um das Ergebnis zu erhalten, nach dem Sie suchen.

Eine binäre Suche beginnt in der Mitte eines sortierten Arrays und bestimmt, auf welcher Seite (falls vorhanden) der Wert, nach dem Sie suchen, aktiviert ist. Diese "Hälfte" des Arrays wird dann erneut auf die gleiche Art und Weise durchsucht, wobei jedes Mal die Ergebnisse halbiert werden.

Answer 4

Ich möchte ein Differenz- brauchen

Für Werte lineare Suche hinzufügen nicht sortiert werden.

Aber für binäre Suche müssen die Werte in sortierter Reihenfolge sein.

Answer 5

Die lineare Suche, auch als sequenzielle Suche bezeichnet, betrachtet jedes Element in der Reihenfolge von Anfang an, um festzustellen, ob das gewünschte Element in der Datenstruktur vorhanden ist. Wenn die Datenmenge klein ist, ist diese Suche schnell. Es ist einfach, aber die benötigte Arbeit ist proportional zur Menge der zu suchenden Daten. Durch die Verdoppelung der Anzahl der Elemente wird die Suchzeit verdoppelt, wenn das gewünschte Element nicht vorhanden ist.

Binäre Suche ist effizient für größere Arrays. In diesem überprüfen wir das mittlere Element. Wenn der Wert größer ist als das, wonach wir suchen, dann schauen Sie in die erste Hälfte, ansonsten schauen Sie in die zweite Hälfte. Wiederholen Sie dies, bis das gewünschte Objekt gefunden wurde. Die Tabelle muss für die binäre Suche sortiert sein. Es eliminiert die Hälfte der Daten bei jeder Iteration. Es ist logarithmisch.

Wenn wir 1000 Elemente zu suchen haben, dauert die binäre Suche etwa 10 Schritte, lineare Suche 1000 Schritte.

Answer 6

binäre Suche läuft in O (log n) Zeit, während lineare Suche läuft in O (n) mal so binäre Suche hat eine bessere Leistung

Answer 7

Stellen Sie sicher, um zu überlegen, ob der Gewinn der schneller binäre Suche ist die Kosten wert die Liste sortiert zu halten (um die binäre Suche nutzen zu können). I.e. Wenn Sie viele Operationen zum Einfügen/Entfernen haben und nur gelegentlich suchen, könnte die binäre Suche insgesamt langsamer als die lineare Suche sein.

Answer 8

Versuchen Sie Folgendes: Wählen Sie einen zufälligen Namen "Nachname, Vorname" und suchen Sie in Ihrem Telefonbuch.

1. Mal: ​​Beginnen Sie am Anfang des Buches, lesen Sie Namen, bis Sie es finden, oder finden Sie den Ort, wo es alphabetisch aufgetreten wäre und beachten Sie, dass es nicht da ist.

Zum zweiten Mal: ​​Öffnen Sie das Buch auf halbem Weg und schauen Sie sich die Seite an. Fragen Sie sich, ob diese Person links oder rechts sein sollte. Welches auch immer es ist, nehmen Sie das 1/2 und finden Sie die Mitte davon. Wiederholen Sie diesen Vorgang, bis Sie die Seite gefunden haben, auf der sich der Eintrag befinden soll, und wenden Sie dann denselben Vorgang auf Spalten an, oder suchen Sie einfach linear nach den Namen auf der Seite wie zuvor.

Zeit beide Methoden und melden Sie zurück!

[auch zu prüfen, was Ansatz besser ist, wenn alles, was Sie haben eine Liste von Namen ist, nicht sortierte ...]

Answer 9

Eine lineare Suche schaut nach unten eine Liste, ein Element zu einem Zeitpunkt, ohne Springen.In Komplexitätsbegriffen ist dies eine O (n) Suche - die Zeit, die benötigt wird, um die Liste zu durchsuchen, wird mit der gleichen Geschwindigkeit größer als die Liste. Wenn Sie mit der Mitte einer sortierten Liste beginnen, sehen Sie, ob der Wert größer oder kleiner als der gesuchte Wert ist, der angibt, ob der Wert in der ersten oder zweiten Hälfte der Sortierung liegt.

Liste. Springe zum halben Weg durch die Unterliste und vergleiche es wieder. Das ist ungefähr so, wie Menschen typischerweise ein Wort in einem Wörterbuch nachschlagen (obwohl wir bessere Heuristiken verwenden, offensichtlich - wenn du nach "Katze" suchst, tust du das nicht Beginnen Sie bei "M"). In Komplexitätsbegriffen ist dies eine O (log n) -Suche - die Anzahl der Suchoperationen wächst langsamer als die Liste, weil Sie den "Suchraum" bei jeder Operation halbieren.

Answer 10

Eine lineare Suche funktioniert, indem jedes Element in einer Liste von Daten untersucht wird, bis es entweder das Ziel findet oder das Ende erreicht. Dies führt zu O (n) Leistung auf einer gegebenen Liste. Eine binäre Suche kommt mit der Voraussetzung, dass die Daten sortiert werden müssen. Wir können diese Informationen nutzen, um die Anzahl der Elemente zu reduzieren, die wir zur Ermittlung unseres Ziels benötigen. Wir wissen, dass wenn wir einen zufälligen Gegenstand in den Daten betrachten (sagen wir der mittlere Gegenstand) und dieser Gegenstand größer ist als unser Ziel, dann sind alle Gegenstände rechts von diesem Gegenstand auch größer als unser Ziel. Das bedeutet, dass wir nur den linken Teil der Daten betrachten müssen. Grundsätzlich können wir jedes Mal, wenn wir nach dem Ziel und dem Fehltreffer suchen, die Hälfte der verbleibenden Elemente eliminieren. Dies gibt uns eine schöne O (log n) Zeitkomplexität.

Denken Sie daran, dass das Sortieren von Daten, selbst mit dem effizientesten Algorithmus, immer langsamer ist als eine lineare Suche (die schnellsten Sortieralgorithmen sind O (n * log n)). Sie sollten also niemals Daten sortieren, um später nur eine einzelne binäre Suche durchzuführen. Wenn Sie jedoch viele Suchvorgänge durchführen (z. B. mindestens O (log n) -Suchen), kann es sinnvoll sein, die Daten so zu sortieren, dass Sie binäre Suchvorgänge ausführen können. Sie können in solchen Situationen auch andere Datenstrukturen wie eine Hash-Tabelle berücksichtigen.

Answer 11

Linear Search durchsucht Elemente, bis der gesuchte Wert gefunden wird.

Effizienz: O(n)

Beispiel Python Code:

test_list = [1, 3, 9, 11, 15, 19, 29] 
test_val1 = 25 
test_val2 = 15 

def linear_search(input_array, search_value): 
    index = 0 
    while (index < len(input_array)) and (input_array[index] < search_value): 
     index += 1 
    if index >= len(input_array) or input_array[index] != search_value: 
     return -1 

    return index 


print linear_search(test_list, test_val1) 
print linear_search(test_list, test_val2) 

Binary Search findet das mittlere Element des Arrays. Überprüft, ob der mittlere Wert größer oder kleiner als der Suchwert ist. Wenn es kleiner ist, erhält es die linke Seite des Arrays und findet das mittlere Element dieses Teils. Wenn es größer ist, wird der richtige Teil des Arrays abgerufen. Der Vorgang wird so lange wiederholt, bis der gesuchte Wert gefunden wird. Oder wenn kein Wert im Array vorhanden ist, wird die Suche beendet.

Effizienz: O(logn)

Beispiel Python Code:

test_list = [1, 3, 9, 11, 15, 19, 29] 
test_val1 = 25 
test_val2 = 15 

def binary_search(input_array, value): 
    low = 0 
    high = len(input_array) - 1 
    while low <= high: 
     mid = (low + high)/2 
     if input_array[mid] == value: 
      return mid 
     elif input_array[mid] < value: 
      low = mid + 1 
     else: 
      high = mid - 1 

    return -1 


print binary_search(test_list, test_val1) 
print binary_search(test_list, test_val2) 

Sie können auch visualisiert Informationen über Lineare und Binäre Suche hier sehen: https://www.cs.usfca.edu/~galles/visualization/Search.html