Welche Speichermethoden und Elementanordnungsanforderungen gelten für Tabellen, die für die binäre Suche geeignet sind?

Die Anforderungen an die Speichermethode und die Elementanordnung der für die binäre Suche geeigneten Tabelle sind: sequentielle Speicherung und die Reihenfolge der Elemente. Die binäre Suche ist eine effizientere Suchmethode. Sie erfordert, dass die lineare Tabelle eine sequentielle Speicherstruktur annimmt und die Elemente in der Tabelle nach Schlüsselwörtern geordnet werden.

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.

Unter der Annahme, dass die Elemente in der Tabelle in aufsteigender Reihenfolge angeordnet sind, vergleichen Sie zunächst das an der mittleren Position der Tabelle erfasste Schlüsselwort mit dem Suchschlüsselwort. Andernfalls ist die Suche erfolgreich Datensatz, um die Tabelle in zwei Untertabellen zu unterteilen, die erste und die letzte. Wenn das in der mittleren Position aufgezeichnete Schlüsselwort größer als das Suchschlüsselwort ist, wird die vorherige Untertabelle weiter durchsucht, andernfalls ist die nächste Untertabelle weiter 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.

Algorithmusanforderungen

1. Es muss eine sequentielle Speicherstruktur verwendet werden.

2. Sie müssen nach Schlüsselwortgröße geordnet werden.

Anzahl der Vergleiche

Berechnungsformel:

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

Wenn die Suche fehlschlägt, werden die Schlüsselwörter mindestens ein Mal verglichen; bei erfolgreicher Suche die maximale Anzahl von Schlüsselwortvergleichen ist b.

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

Erklärung

Die Halbsuchmethode wird auch als binäre Suchmethode bezeichnet. Sie nutzt die Ordnungsbeziehung zwischen Elementen vollständig aus und übernimmt die Divide-and-Conquer-Strategie, um die Suchaufgabe in O(log n) abzuschließen. im schlimmsten Fall. 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= Wenn x < für x.

Weitere Informationen zu diesem Thema finden Sie auf: Chinesische PHP-Website!

Das obige ist der detaillierte Inhalt vonWelche Speichermethoden und Elementanordnungsanforderungen gelten für Tabellen, die für die binäre Suche geeignet sind?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!