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 x
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!
