binärer Suchalgorithmus

Die binäre Suche wird auch als binäre Suche bezeichnet und ist eine effizientere Suchmethode. Die binäre Suche erfordert jedoch, dass die lineare Tabelle eine sequentielle Speicherstruktur annimmt und die Elemente in der Tabelle nach Schlüsselwörtern geordnet werden müssen.

Suchprozess

Angenommen, die Elemente in der Tabelle sind in aufsteigender Reihenfolge angeordnet, notieren Sie zunächst den Schlüssel in der Mitte der Tabelle Das Wort wird mit dem Suchschlüsselwort verglichen. Wenn die beiden gleich sind, ist die Suche erfolgreich. Andernfalls wird der mittlere Positionsdatensatz verwendet, um die Tabelle in die erste und letzte Untertabelle zu unterteilen Wenn der in der mittleren Position aufgezeichnete Wert größer als das Suchwort ist, wird die vorherige Untertabelle weiter durchsucht, andernfalls wird weiter nach der nächsten Untertabelle gesucht. Wiederholen Sie den obigen Vorgang, bis ein Datensatz gefunden wird, der die Bedingungen erfüllt, wodurch die Suche erfolgreich ist, oder bis die Untertabelle nicht mehr vorhanden ist. In diesem Fall schlägt die Suche fehl.

Anzahl der Vergleiche

Berechnungsformel:

Wenn die Sequenztabelle n Schlüsselwörter enthält:

Wenn die Suche fehlschlägt, vergleichen Sie das Schlüsselwort mindestens ein Mal. Wenn die Suche erfolgreich ist, beträgt die maximale Anzahl an Schlüsselwortvergleichen b.

Hinweis: a, b, n sind alle positive ganze Zahlen.

Algorithmuskomplexität

Die Grundidee der binären Suche besteht darin, n Elemente in zwei ungefähr gleiche Teile zu teilen und a[n/2] mit x zu vergleichen, Wenn x=a[n/2], dann wird x gefunden und der Algorithmus wird beendet, wenn xa[. n/2], dann suchen Sie einfach nach x in der rechten Hälfte des Arrays a.

Die zeitliche Komplexität ist nichts anderes als die Anzahl der While-Schleifen!

Es gibt insgesamt n Elemente,

folgen nach und nach n, n/2, n/4, .... n/2^k (die verbleibende Anzahl von Elementen wird als nächstes bearbeitet). ), wobei k die Anzahl der Zyklen ist

Da Ihr n/2^k gerundet ist >=1

, also n/2^k=1

kann erhalten werden k=log2n, (es ist der Logarithmus von n zur Basis 2)

Die Zeitkomplexität kann also ausgedrückt werden als O(h)=O(log2n)

Nachfolgend finden Sie eine Halbierung. Finden Sie den Pseudocode der Implementierung:

BinarySearch(max,min,des)

mid-<(max+min)/2

while(min< =max)

mid=(min+max)/2

if mid=des then

return mid

elseif mid >des then

max=mid-1

else

min=mid+1

return max

Half search Diese Methode wird auch als binäre Suche bezeichnet. Diese Methode nutzt die Ordnungsbeziehung zwischen Elementen vollständig aus und übernimmt die Divide-and-Conquer-Strategie, die im schlimmsten Fall die Suchaufgabe in O (log n) abschließen kann. Seine Grundidee ist: (unter der Annahme, dass die Array-Elemente in aufsteigender Reihenfolge angeordnet sind) n Elemente in zwei Hälften mit ungefähr der gleichen Anzahl teilen, a[n/2] nehmen und es mit dem x vergleichen, das Sie finden möchten, wenn x= a[n/ 2] dann wird x gefunden und der Algorithmus endet; wenn x

Das obige ist der detaillierte Inhalt vonbinärer Suchalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!