WikiDer > Bisektion

Halbierung (aus dem Lateinischen: 'halbieren') oder binäre Suche ist eine Methode zum Auffinden eines Elements in einer Menge, das ein bestimmtes Kriterium erfüllen muss, indem immer die Teilmenge der möglichen zu suchenden Werte geteilt wird.

Das Verfahren funktioniert nur, wenn schnell festgestellt werden kann, ob sich das gesuchte Element in der einen Hälfte oder in der anderen Hälfte der noch möglichen Werte befindet. In der Praxis bedeutet dies normalerweise, dass die Menge the bestellt muss sein.

Beispiel

Sucht wo in der geordneten Zahlenfolge ${displaystyle a_{0}$ das Element 7 befindet. Vergleiche das Element ${displaystyle a_{5}=13}$ ungefähr in der Mitte der 7er-Reihe. Da 7 kleiner als 13 ist, sollte 7 im linken Teil der Reihe stehen, ansonsten im rechten Teil. Vom linken Teil ist das Element auf halbem Weg, ${displaystyle a_{2}=5}$, wieder mit 7 verglichen. Da 5 kleiner als 7 ist, steht 7 anscheinend rechts von 7, also mit den Elementen ${displaystyle a_{3}}$ und ${displaystyle a_{4}}$. Noch vergleichen ${displaystyle a_{4}}$ mit 7; ${displaystyle a_{4}=11}$, also 7 ist links von ${displaystyle a_{4}}$, So ${displaystyle a_{3}=7}$.

Die binäre Suche ist die übliche Methode, um etwas in einem Wörterbuch nachzuschlagen. Man schlägt das Buch ungefähr in der Mitte auf und sieht dann, ob das gesuchte Wort in der ersten oder zweiten Hälfte des Buches gesucht werden soll. Die Suche wird in dieser Hälfte fortgesetzt. In der Praxis weiß man bereits ungefähr, in welcher Stelle des Buches gesucht werden soll: Beginnt das gesuchte Wort mit einem A, dann fängt man nicht in der Mitte des Buches an. Dadurch wird das Verfahren noch effizienter - siehe unten bei #Wirksamkeit.

Rekursive Implementierung in C

Das nächste Fragment von a C Programm implementiert a rekursiv Bisektionsalgorithmus:

#einschließen<iostream>mitNamensraumstd;boolbinary_search_rec(int*Werte,intSuche,intl,intr){wenn(l==r){// binäre Suche ist auf 1 Zelle beschränkt, an der das gesuchte Element erwartet wird.RückkehrWerte[l]==Suche;}sonst{// Mittelpunkt zwischen linker (l) und rechter (r) Grenze bestimmen determineintich=(lr)/2;// Division von 2 ganzen Zahlen bleibt int, abgerundet: 7/2 = 3wenn(Werte[ich]<Suche){// im rechten Teil weitersuchen [m 1 , r]Rückkehrbinary_search_rec(Werte,Suche,ich1,r);}sonst{// im linken Teil weitersuchen [l, m]Rückkehrbinary_search_rec(Werte,Suche,l,ich);}}}boolbinäre Suche(int*Werte,intNummer,intSuche){// starte die Rekursion mit:// l: linke Grenze unserer Tabelle = 0// r: rechte Grenze unserer Tabelle = Anzahl der Elemente -1// search: der gesuchte WertRückkehrbinary_search_rec(Werte,Suche,0,Nummer-1);}intMain(intargc,constverkohlen*argv[]){intWerte[]={9,13,17,19,25,26,29,40};// Barwert nachschlagen, zum Beispiel 13cout<<(binäre Suche(Werte,8,13)?"vorhanden":"abwesend")<<endl;// fehlenden Wert nachschlagen, z.B. 16cout<<(binäre Suche(Werte,8,16)?"vorhanden":"abwesend")<<endl;}

Lineare Implementierung in C

Das folgende Snippet implementiert einen linearen Bisektionsalgorithmus:

boolAnordnungsliste::finden(verkohlen*sFinden,// gesuchte Zeichenfolgeverkohlen**aStr,// Sammlung von Strings, in denen gesucht werden sollintnNIitems,// Anzahl der Strings in der Sammlungint*piEinfügen// Einfügepunkt zum Zurückgeben){/* Diese Methode verwendet Bisektion: teilt das zu durchsuchende Stück    * immer halbieren und immer eine Seite beurteilen    * der neuen Schnittebene. */intiL=0;intiR=nNIitems;intnSpanien=iR-iL;boolbSuchen=(nSpanien>0);intim=iLnSpanien/2;boolbGefunden=falsch;während(bSuchen){verkohlen*sN=aStr[im];intnCmp=strcmp(sFinden,sN);wenn(nCmp>0){/* gesuchte Zeichenfolge befindet sich im oder direkt rechts vom rechten Teil */iL=im;}sonstwenn(nCmp<0){/* gesuchte Zeichenfolge befindet sich im oder direkt links vom linken Teil */iR=im;}sonst{bGefunden=wahr;Unterbrechung;}wenn(nSpanien==1){wenn(nCmp>0){im=iR;}sonst{im=iL;}Unterbrechung;// nicht gefunden; Einfügepunkt ja}nSpanien=iR-iL;im=iLnSpanien/2;}// Ende der Suchschleife*piEinfügen=im;// Einfügepunkt oder Position des gefundenen StringsRückkehrbGefunden;// wenn false: iN ist der Einfügepunkt, sonst die Position des gefundenen Strings}

Anwendung auf mathematische Funktionen

spät ${displaystyle xightarrow f(x)}$ ein eintöniger Aufgang Funktion sein. Um den Wert von zu erhalten ${Anzeigestil x}$ zu gegebener Zeit ${Anzeigestil f(x)=a}$ zu finden ist jetzt Bisektion, um zu verwenden ${Anzeigestil x}$ zu nähern.

Als Beispiel könnte der obige Programmausschnitt dienen, mit folgenden Hinweisen:

• verkohlen*sSuchen: der angegebene Wert a;
• verkohlen** aStr: die Stellenbeschreibung;
• int nNIitems: iL und iR, eine Schätzung der Fläche, in der x liegt, als Gleitkommazahlen;
• verkohlen* sN= aStr[iN]: Berechnung eines Funktionswertes für eine Approximation von x;
• wenn (nSpan==1): Testet, ob die gewünschte Genauigkeit erreicht wurde.

Der 'Einfügepunkt' ist jetzt die Näherung mit einem Fehler von (iR - iL).

Effizienz

Bei Annäherung an einen Funktionswert halbiert sich der Fehler mit jedem Schritt, dh wir erhalten eine Dezimalstelle pro (mehr als) drei Zyklen (drei Dezimalstellen pro 10 Zyklen). Bei Anwendung auf diskrete Werte sind 1000 Zahlen in 10 Zyklen durchsuchbar, 1.000.000 in 20 und so weiter. Die Anzahl der Schritte bis zur gewünschten Genauigkeit ist durch die Bisektion im Voraus bekannt.

Während die Bisektion zuverlässig und einfach ist, gibt es Methoden, die in vielen Fällen besser funktionieren, insbesondere wenn sie auf mathematische Funktionen angewendet werden. Solche Methoden verwenden (eine Schätzung der) Steigung am oder um den letzten gefundenen Punkt. Für Funktionen ohne springt und Nicken von Punkten, die ungefähr in Richtung des gewünschten Punktes liegen, so dass die nächste Annäherung im Durchschnitt besser ist, als es bei der Bisektion gewesen wäre. Beispiele sind die Methode von Newton-Raphson und regelmäßig falsch.

Siehe auch

• Halbierungsmethode