Die lineare Suche und die binäre Suche sind gängige Algorithmen, die verwendet werden, um Elemente innerhalb einer Liste zu finden. Das Verständnis der erwarteten Anzahl von Vergleichen, die jeder Algorithmus durchführt, kann bei der Auswahl der effizientesten Methode für bestimmte Situationen helfen.

Lineare Suche

Die lineare Suche überprüft jedes Element der Liste sequentiell, bis es das Ziel findet oder das Ende erreicht. Die erwartete Anzahl von Vergleichen hängt davon ab, ob das Ziel vorhanden ist und seine Position in der Liste.

Wenn die Liste n Elemente enthält und das Ziel gleichermaßen wahrscheinlich an jeder Position ist, ist die erwartete Anzahl von Vergleichen:

Erwartete Vergleiche = (n + 1) / 2

Dies liegt daran, dass die Suche im Durchschnitt das Ziel auf halbem Weg durch die Liste findet.

Binäre Suche

Die binäre Suche funktioniert auf sortierten Listen, indem das Suchintervall wiederholt halbiert wird.

Im besten Fall befindet sich das Ziel in der Mitte, was nur einen Vergleich erfordert. Im schlimmsten Fall dauert es ungefähr log2 n Vergleiche.

Angenommen, das Ziel ist ebenso wahrscheinlich, an jeder Position zu sein, ist die erwartete Anzahl von Vergleichen ungefähr:

Erwartete Vergleiche ≈ log2 n

Vergleichszusammenfassung

  • Die lineare Suche hat eine erwartete Vergleichszahl von (n + 1) / 2.
  • Die binäre Suche hat eine erwartete Vergleichszahl von ungefähr log2 n.
  • Binäre Suche erfordert in der Regel weniger Vergleiche für große Listen.
  • Lineare Suche kann für kleine oder unsortiert Listen vorzuziehen sein.