Binäre Suche

1. Binäre Suche
Die binäre Suche wird auch als halbe Suche bezeichnet.
Anforderungen für die binäre Suche: Die lineare Tabelle ist eine geordnete Liste, dh die Knoten in der Tabelle sind nach Schlüsselwörtern geordnet und Vektoren werden als Speicherstruktur der Tabelle verwendet. Es kann davon ausgegangen werden, dass die Sequenztabelle in aufsteigender Reihenfolge vorliegt.

2. Die Grundidee der binären Suche
Die Grundidee der binären Suche ist: (vorausgesetzt, R[low..high] ist das aktuelle Suchintervall)
(1) Bestimmen Sie zuerst die Mitte des Intervalls. Position:
(2) Vergleichen Sie dann den zu überprüfenden k-Wert mit R [mid] .key: Wenn gleich, finden Sie erfolgreich und kehren Sie zu dieser Position zurück, andernfalls müssen Sie die bestimmen Neuer Suchbereich und setzen Sie die Zweipunktsuche fort, um zu finden. Die spezifische Methode lautet wie folgt:
①Wenn R[mid].key>K, dann ist aus der Ordnung der Tabelle ersichtlich, dass R[mid. .n].keys sind alle größer als K. Wenn es also Schlüssel gleich K im Tabellenknoten gibt, muss sich der Knoten in der Untertabelle R[1..mid-1] links von der Position mid befinden, also die Neues Suchintervall ist die linke Untertabelle R[1..mid-1].
②Wenn R[mid].key Daher kann ausgehend vom anfänglichen Suchintervall R[1..n] bei jedem Vergleich mit dem Knotenschlüsselwort an der Mittelpunktposition des aktuellen Suchintervalls festgestellt werden, ob die Suche erfolgreich ist Ist dies nicht erfolgreich, wird das aktuelle Suchintervall um die Hälfte reduziert. Dieser Vorgang wird wiederholt, bis der Knoten mit dem Schlüssel K gefunden wird oder bis das aktuelle Suchintervall leer ist (d. h. die Suche fehlschlägt).

3. Binärer Suchalgorithmus

int BinSearch(SeqList R, KeyType K)
{ //Führen Sie eine binäre Suche in der geordneten Liste R[1..n] durch und geben Sie den Knoten zurück, wenn erfolgreiche Position, gibt Null zurück, wenn fehlgeschlagen
int low=1, high=n, mid; //Legen Sie den Anfangswert der oberen und unteren Grenzen des aktuellen Suchintervalls fest
while(low<=high){ / /Aktuelles Suchintervall R [low..high] non-empty
mid=(low+high)/2;
if(R[mid].key==K) return mid; //Die Suche ist erfolgreich und gibt
if(R [MID] .kdy & gt; k)
High = mid-1; // Siehe
Else
Low = MID+1 in R [Low.. Mid -]; // Weiter in R-Suche
in [mid+1..high] }
                                                                                                                                                                                                                                                          Es ist einfach, sein rekursives Programm anzugeben [siehe Übungen]

4. Der Ausführungsprozess des binärer Suchalgorithmus
Angenommen, die geordnete Folge von Schlüsselwörtern in der Eingabeinstanz des Algorithmus ist

(05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92)

Die Das zu findende Schlüsselwort K ist 21 bzw. 85. Der spezifische Suchprozess [siehe Animationsdemonstration]

5. Binärer Suchentscheidungsbaum
Der binäre Suchprozess kann durch einen Binärbaum beschrieben werden: Nehmen Sie den Knoten in der Mitte des aktuellen Suchintervalls als Wurzel , die linke Untertabelle und die rechte Untertabelle. Die Knoten in der Untertabelle dienen als linker Unterbaum bzw. rechter Unterbaum der Wurzel. Der resultierende Binärbaum wird als Entscheidungsbaum (Decision Tree) oder Vergleichsbaum (Comparison Tree) bezeichnet, der die binäre Suche beschreibt.

Hinweis:

Die Form des Entscheidungsbaums hängt nur von der Anzahl der Tabellenknoten n ab und hat nichts mit dem Wert von R[1..n].keys in der Eingabeinstanz zu tun.
[Beispiel] Eine geordnete Liste mit 11 Knoten kann durch den in der folgenden Abbildung gezeigten Entscheidungsbaum dargestellt werden.



(1) Die Zusammensetzung des binären Suchentscheidungsbaums
① Der Kreisknoten ist der interne Knoten im Baum. Die Zahl innerhalb des Kreisknotens im Baum gibt die Position des Knotens in der geordneten Liste an.

　②Externer Knoten: Alle Nullzeiger im Kreisknoten werden durch einen virtuellen quadratischen Knoten, also den externen Knoten, ersetzt.

③Die Markierungen „<“, „(“, „>“, „)“ auf dem linken (rechten) Zweig, der einen Knoten i mit seinem linken (rechten) Kind im Baum verbindet, zeigen an: wann das Schlüsselwort sein soll Wenn KR[i].key) durchsucht wird, sollten Sie den linken (rechten) Zweig nehmen, um das linke (rechte) Kind von i zu erreichen, und das Schlüsselwort des Kindes weiter mit K vergleichen. Wenn sie gleich sind, wird der Suchvorgang beendet und zurückgegeben; andernfalls wird K weiterhin mit dem Knoten auf der unteren Ebene im Baum verglichen.

(2) Durchsuchen des Entscheidungsbaums für die binäre Suche
Bei der binären Suche wird der gegebene Wert K mit dem Schlüsselwort des Wurzelknotens des Entscheidungsbaums für die binäre Suche verglichen. Bei Gleichstand Erfolg. Andernfalls, wenn er kleiner als der Schlüssel des Wurzelknotens ist, suchen Sie im linken Teilbaum. Wenn das Schlüsselwort größer als der Wurzelknoten ist, suchen Sie im rechten Teilbaum.
[Beispiel] Wenn bei einer Tabelle mit 11 Knoten der gesuchte Knoten der 6. Knoten in der Tabelle ist, ist nur ein Vergleich erforderlich. Wenn der gesuchte Knoten der 3. oder 9. Knoten in der Tabelle ist, sind zwei Vergleiche erforderlich sind drei Vergleiche erforderlich, um den 1., 4., 7. und 10. Knoten zu finden; vier Vergleiche sind erforderlich, um den 2., 5., 8. und 11. Knoten zu finden.
Es ist ersichtlich, dass der erfolgreiche binäre Suchprozess genau einen Pfad von der Wurzel des Entscheidungsbaums zum überprüften Knoten nimmt und die Anzahl der verglichenen Schlüsselwörter genau der Anzahl der Ebenen des Knotens im Knoten entspricht Baum. Wenn die Suche fehlschlägt, durchläuft der Vergleichsprozess einen Pfad von der Wurzel des Entscheidungsbaums zu einem externen Knoten, und die erforderliche Anzahl von Schlüsselwortvergleichen entspricht der Gesamtzahl der internen Knoten auf dem Pfad.
【Beispiel】 Die Schlüsselwortsequenz der nachzuschlagenden Tabelle lautet: (05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92). Die internen Knoten des Prozesses sind 6, 9 und 10, und schließlich erreicht er den quadratischen Knoten „9-10“, und die Anzahl seiner Vergleiche beträgt 3.
Tatsächlich bedeutet „i-i+1“ im quadratischen Knoten, dass der zu suchende Wert K zwischen R[i].key und R[i+1].key liegt, d. h. R[i] .key

(3) Die durchschnittliche Suchlänge der binären Suche
Angenommen, die Gesamtzahl der internen Knoten beträgt n=2h-1, dann ist der Beurteilungsbaum ein vollständiger Binärbaum mit einer Tiefe von h=lg( n+1) (Tiefe h beinhaltet keine externen Knoten). Die Anzahl der Knoten auf der k-ten Ebene des Baums beträgt 2k-1 und die Anzahl der zu ihrer Suche erforderlichen Vergleiche beträgt k. Unter der Annahme gleicher Wahrscheinlichkeit beträgt die durchschnittliche Suchlänge bei erfolgreicher binärer Suche: Die Tiefe des Baums. Im schlimmsten Fall übersteigt die Anzahl erfolgreicher Vergleiche nicht die Tiefe des Entscheidungsbaums. Das heißt:
 
Die schlechteste Leistung und die durchschnittliche Leistung der binären Suche liegen ziemlich nahe beieinander.

6. Vor- und Nachteile der binären Suche

Obwohl die binäre Suche effizient ist, muss die Tabelle nach Schlüsselwörtern sortiert werden. Das Sortieren selbst ist ein sehr zeitaufwändiger Vorgang. Selbst die Verwendung einer effizienten Sortiermethode wird O(nlgn) Zeit in Anspruch nehmen.

Die binäre Suche gilt nur für sequentielle Speicherstrukturen. Um die Reihenfolge der Tabelle aufrechtzuerhalten, müssen beim Einfügen und Löschen in der sequentiellen Struktur viele Knoten verschoben werden. Daher eignet sich die binäre Suche besonders für lineare Tabellen, die nach ihrer Erstellung selten geändert werden und häufig durchsucht werden müssen.
Für lineare Tabellen, die nur wenige Suchvorgänge erfordern und häufig geändert werden müssen, können verknüpfte Listen als Speicherstrukturen für sequentielle Suchvorgänge verwendet werden. Die binäre Suche kann nicht für verknüpfte Listen implementiert werden.

Biäre Sortierung

#include

#include

void TwoInsertSort(int array[],int n)
{
int left,right,num;
int middle,j,i;
for(i = 1;i < n;i++)
{
left = 0;/ / Vorbereiten
                                                                                                                             middle = ( left + right ) / 2; // Zeigen Sie auf die sortierte mittlere Position
if( num < array[middle] )// Das einzufügende Element sollte im linken Bereich liegen
right = middle-1;
else else // Das einzufügende Element sollte im rechten Intervall liegen
left = middle+1;
}
for( j = i-1;j >= left;j-- )//Zurückbewegen Datensätze mit Sortiercode größer als R[i]
            array[j+1] = array[j];

int rcmp( const int *a, const int *b)
{
return (*a-*b);
}
void main()
{
int array[50];
int i;
printf("Das ursprüngliche Array ist :n");
for( i=0; i<50; i++ )//Array-Initialisierung und -Anzeige
{
array[i] = 50-i;
printf("array[%d]:%dn", i, array[i]);
}
TwoInsertSort(array,sizeof (array)/sizeof(int));//Binäre Sortierung
printf("nAfter sorted :n");
for( i=0; i<50; i++ )
printf("array [ %d]:%dn", i, array[i]);

//Bibliotheksfunktion bsearch verwendet die Binärmethode, um eine bestimmte Zahl in einem geordneten Array zu finden und gibt die Adresse der Zahl zurück

a = (int *)bsearch(&b, numarray, sizeof(numarray)/sizeof(numarray[0]), sizeof(int),rcmp);

}

Weitere Artikel zur Dichotomiesuche finden Sie auf der chinesischen PHP-Website!