wake-up-neo.com

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

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

39
Smi

Ein lineare Suche sucht eine Liste nach dem anderen ab, ohne zu springen. In Bezug auf die Komplexität ist dies eine O(n)-Suche - die Suchzeit für die Liste wird mit der gleichen Geschwindigkeit wie die Liste erhöht.

Ein Binäres Suchen beginnt, wenn Sie mit der Mitte einer sortierten Liste beginnen und feststellen, ob der Wert größer oder kleiner als der gesuchte Wert ist, der bestimmt, ob der Wert in der ersten oder zweiten Hälfte liegt der Liste. Springe zur Hälfte durch die Unterliste und vergleiche es noch einmal. Dies ist so, wie Menschen normalerweise ein Wort in einem Wörterbuch nachschlagen (obwohl wir natürlich bessere Heuristiken verwenden - wenn Sie nach "Katze" suchen, tun Sie dies nicht Beginne bei "M"). In Bezug auf die Komplexität ist dies eine O(log n)-Suche - die Anzahl der Suchvorgänge wächst langsamer als die Liste, da Sie mit jeder Operation den "Suchraum" halbieren.

Angenommen, Sie haben in einer A-Z-Buchstabenliste nach U gesucht (Index 0-25; wir suchen den Wert in Index 20).

Eine lineare Suche würde fragen:

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

Die binäre Suche würde fragen:

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

Vergleich der beiden:

  • Bei der binären Suche müssen die Eingabedaten sortiert werden. lineare Suche nicht
  • Die binäre Suche erfordert einen Vergleich von ordering; Für die lineare Suche sind nur Gleichheitsvergleiche erforderlich
  • Die binäre Suche hat die Komplexität O (log n); Die lineare Suche hat die Komplexität O(n), wie zuvor erläutert
  • Bei der binären Suche ist ein wahlfreier Zugriff auf die Daten erforderlich. Die lineare Suche erfordert nur einen sequentiellen Zugriff (dies kann sehr wichtig sein - eine lineare Suche kann stream - Daten beliebiger Größe).
108
Jon Skeet

Betrachten Sie es als zwei verschiedene Wege, um sich in einem Telefonbuch zurechtzufinden. Eine lineare Suche beginnt am Anfang und liest jeden Namen, bis Sie finden, wonach Sie suchen. Eine binäre Suche dagegen ist, wenn Sie das Buch öffnen (normalerweise in der Mitte), den Namen oben auf der Seite anzeigen und entscheiden, ob der gewünschte Name größer oder kleiner als der von Ihnen gesuchte ist suche nach Wenn der Name, nach dem Sie suchen, größer ist, suchen Sie auf diese Weise den oberen Teil des Buches weiter. 

58
Mia Clarke

Bei einer linearen Suche wird jedes Element in einer Datenliste betrachtet, bis es entweder das Ziel findet oder das Ende erreicht. Dies führt zu einer Leistung von O(n) in einer gegebenen Liste. Eine binäre Suche setzt voraus, dass die Daten sortiert werden müssen. Wir können diese Informationen nutzen, um die Anzahl der Elemente zu verringern, die wir betrachten müssen, um unser Ziel zu finden. Wenn wir ein zufälliges Element in den Daten betrachten (beispielsweise das mittlere Element) und dieses Element größer als unser Ziel ist, wissen wir, dass alle Elemente rechts neben diesem Element auch unser Ziel übersteigen. Dies 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 Fehlschuss suchen, die Hälfte der verbleibenden Gegenstände entfernen. Dies gibt uns eine Nice O (log n) Zeitkomplexität. 

Denken Sie daran, dass das Sortieren von Daten selbst mit dem effizientesten Algorithmus immer langsamer ist als bei einer linearen Suche (die schnellsten Sortieralgorithmen sind O (n * log n)). Sie sollten also niemals Daten sortieren, um später eine einzige binäre Suche durchzuführen. Wenn Sie jedoch viele Suchen durchführen (sagen Sie mindestens O (log n) Suchen), kann es sich lohnen, die Daten so zu sortieren, dass Sie binäre Suchen durchführen können. Sie können auch andere Datenstrukturen wie eine Hashtabelle in solchen Situationen berücksichtigen. 

14
antar

Eine lineare Suche beginnt am Anfang einer Werteliste und prüft 1 nach 1, um das gewünschte Ergebnis zu erhalten.

Eine binäre Suche beginnt in der Mitte eines sortierten Arrays und bestimmt, auf welcher Seite (falls vorhanden) der Wert liegt, nach dem Sie suchen. Diese "Hälfte" des Arrays wird dann auf dieselbe Weise erneut gesucht, wobei die Ergebnisse jeweils durch zwei Hälften geteilt werden.

5
jthompson

Stellen Sie sicher, dass Sie darüber nachdenken, ob der Gewinn der schnelleren binären Suche die Kosten der Sortierung der Liste wert ist (um die binäre Suche verwenden zu können). Das heißt Wenn Sie viele Einfüge-/Entfernungsvorgänge haben und nur gelegentlich suchen, kann die binäre Suche insgesamt langsamer sein als die lineare Suche.

5
knweiss

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

1. Mal: ​​Beginnen Sie am Anfang des Buches, lesen Sie die Namen, bis Sie sie finden, oder suchen Sie den Ort, an dem sie alphabetisch vorgekommen wäre, und beachten Sie, dass sie nicht vorhanden ist.

2. Mal: ​​Öffnen Sie das Buch auf halbem Weg und schauen Sie sich die Seite an. Fragen Sie sich, ob diese Person links oder rechts ist. Was auch immer es ist, nimm diesen 1/2 und finde die Mitte davon. Wiederholen Sie diesen Vorgang, bis Sie die Seite gefunden haben, auf der sich der Eintrag befinden soll, und wenden Sie dann entweder den gleichen Prozess auf Spalten an oder suchen Sie einfach entlang der Namen auf der Seite wie zuvor.

Zeit beide Methoden und Bericht zurück!

[Überlegen Sie sich auch, welche Vorgehensweise besser ist, wenn Sie nur eine Liste von Namen haben, nicht sortiert ...].

3
simon

Bei einer linearen Suche wird eine Liste einzeln nach unten durchsucht, ohne zu springen. In Bezug auf die Komplexität ist dies eine Suche nach O(n). Die Zeit für das Durchsuchen der Liste wird mit derselben Geschwindigkeit größer als die Liste.

Eine binäre Suche beginnt, wenn Sie mit der Mitte einer sortierten Liste beginnen und feststellen, ob diese größer oder kleiner als der Wert ist, nach dem Sie suchen, wodurch bestimmt wird, ob sich der Wert in der ersten oder zweiten Hälfte der Liste befindet. Springe zur Hälfte durch die Unterliste und vergleiche es noch einmal. Dies ist so, wie Menschen normalerweise ein Wort in einem Wörterbuch nachschlagen (obwohl wir natürlich bessere Heuristiken verwenden - wenn Sie nach "Katze" suchen, tun Sie dies nicht Beginne bei "M"). In Bezug auf die Komplexität ist dies eine O (log n) -Suche - die Anzahl der Suchvorgänge wird langsamer als in der Liste, da Sie mit jeder Operation den "Suchraum" halbieren.

2
Vijay

die binäre Suche wird in O(logn) - Zeit ausgeführt, während die lineare Suche in O(n) - Zeiten ausgeführt wird 

2
Vijay

Die lineare Suche, auch als sequentielle Suche bezeichnet, sucht von Anfang an nacheinander jedes Element, um festzustellen, ob das gewünschte Element in der Datenstruktur vorhanden ist. Wenn die Datenmenge klein ist, ist diese Suche schnell. Diese Arbeit ist einfach, aber die erforderliche Arbeit steht im Verhältnis zu der zu durchsuchenden Datenmenge. Die Verdoppelung der Anzahl der Elemente verdoppelt die Suchzeit, wenn das gewünschte Element nicht vorhanden ist.

Die binäre Suche ist für größere Arrays effizient. In diesem prüfen wir das mittlere Element. Wenn der Wert größer ist als der, nach dem wir suchen, dann schauen Sie in die erste Hälfte, ansonsten schauen Sie in die zweite Hälfte. Wiederholen Sie dies, bis der gewünschte Artikel gefunden ist. Die Tabelle muss für die binäre Suche sortiert werden. Bei jeder Iteration entfällt die Hälfte der Daten. Logarithmisch.

Wenn 1000 Elemente zu suchen sind, dauert die binäre Suche etwa 10 Schritte, bei einer linearen Suche 1000 Schritte.

2
Prabhu. S

Für ein klares Verständnis werfen Sie einen Blick auf meine Codepen-Implementierungen https://codepen.io/serdarsenay/pen/XELWqN

Der größte Unterschied besteht darin, dass Sie Ihr Sample vor der binären Suche sortieren müssen. Daher können Samples für die meisten "normal großen" (dh umstrittenen) Proben mit einem linearen Suchalgorithmus schneller gesucht werden.

Hier ist der Javascript-Code, für HTML und CSS und ein ausführliches Beispiel siehe den obigen Codepen-Link.

var unsortedhaystack = [];
var haystack = [];
function init() {
  unsortedhaystack = document.getElementById("haystack").value.split(' ');
}
function sortHaystack() {
  var t = timer('sort benchmark');
  haystack = unsortedhaystack.sort();
  t.stop();
}

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log('Timer:', name, 'finished in', time, 'ms');
        }
    }
};

function lineerSearch() {
  init();
  var t = timer('lineerSearch benchmark');
  var input = this.event.target.value;
  for(var i = 0;i<unsortedhaystack.length - 1;i++) {
    if (unsortedhaystack[i] === input) {
      document.getElementById('result').innerHTML = 'result is... "' + unsortedhaystack[i] + '", on index: ' + i + ' of the unsorted array. Found' + ' within ' + i + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return unsortedhaystack[i]; 
    }
  }
}

function binarySearch () {
  init();
  sortHaystack();
  var t = timer('binarySearch benchmark');
  var firstIndex = 0;
  var lastIndex = haystack.length-1;
  var input = this.event.target.value;

  //currently point in the half of the array
  var currentIndex = (haystack.length-1)/2 | 0;
  var iterations = 0;

  while (firstIndex <= lastIndex) {
    currentIndex = (firstIndex + lastIndex)/2 | 0;
    iterations++;
    if (haystack[currentIndex]  < input) {
      firstIndex = currentIndex + 1;
      //console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);
    } else if (haystack[currentIndex] > input) {
      lastIndex = currentIndex - 1;
      //console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);
    } else {
      document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return true;
    }
  }
}
0
serdarsenay

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, wird die linke Seite des Arrays abgerufen und das mittlere Element dieses Teils gefunden. Wenn es größer ist, wird der richtige Teil des Arrays abgerufen. Es wiederholt die Operation, bis der gesuchte Wert gefunden wird. Oder wenn das Array keinen Wert enthält, 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)

Visualisierte Informationen zur linearen und binären Suche finden Sie auch hier: https://www.cs.usfca.edu/~galles/visualization/Search.html

0
Can Uludağ