Was ist die binäre Suche in einer geordneten Liste?

Halbe Suche der geordneten Liste: Wenn der angegebene Wert dem Schlüssel des mittleren Datensatzes entspricht, ist die Suche erfolgreich. dann ist die Suche auf der linken Seite des mittleren Datensatzes erfolgreich. Setzen Sie die Suche im halben Bereich fort.

Die Betriebsumgebung dieses Artikels: Windows 7-System, Dell G3-Computer.

Konzept der Halbsuche:

Suche nach der Hälfte, auch als binäre Suche bekannt.

Die Voraussetzung ist, dass die Datensätze in der linearen Tabelle in der Schlüsselreihenfolge vorliegen müssen (von klein nach groß oder von groß nach klein) und die lineare Tabelle nacheinander gespeichert werden muss.

Die Grundidee der Halbwertsuche ist: Nehmen Sie in einer geordneten Liste den Mittelwert als Vergleichsobjekt. Wenn der angegebene Wert dem Schlüssel des Mittelwerts entspricht, ist die Suche erfolgreich Der Wert ist kleiner als der Schlüsselwort des mittleren Datensatzes. Setzen Sie die Suche in der linken Hälfte des mittleren Datensatzes fort. Wiederholen Sie den obigen Vorgang, bis die Suche erfolgreich ist oder nicht in allen Bereichen ein Datensatz vorhanden ist und die Suche fehlschlägt.

Algorithmusimplementierung:

public int Binary_Search(int[] a, int n, int key) {
int low = 1, high = n, mid;
while(low <= high) {
mid = (int)((low + high) / 2);
if(key < a[mid]) {
high = mid - 1;
}
else if(key > a[mid]) {
low = mid + 1;
}
else return mid;
}
return 0;
}

verwendet normalerweise drei Zeiger: niedrig, hoch und mittel. Stellen Sie jeweils den Wertindex ganz links im Suchbereich, den Wertindex ganz rechts im Suchbereich und den Index des aktuellen Vergleichswerts dar.

Zeitkomplexitätsanalyse:

Die halbe Suche entspricht tatsächlich der Aufteilung der statisch geordneten Nachschlagetabelle in zwei Teilbäume, dh während der Suche muss nur die Hälfte der Daten gefunden werden, was bedeutet, dass die Arbeitsbelastung um die Hälfte reduziert wird um die Effizienz zu verbessern.

Empfehlungen für entsprechende Videos: PHP-Programmierung vom Einstieg bis zum Master

Das obige ist der detaillierte Inhalt vonWas ist die binäre Suche in einer geordneten Liste?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!