Bisectie
Bisectie (uit het latijn: 'in tweeën snijden') is een methode om een bepaalde waarde in een verzameling te vinden door de af te zoeken ruimte steeds te halveren.
De methode werkt alleen als snel kan worden vastgesteld of de gezochte waarde zich in de ene of in de andere halfruimte bevindt. In de praktijk betekent dat meestal dat de verzameling gesorteerd moet zijn.
Inhoud |
[bewerk] Voorbeeld
Neem een gesorteerde getallenrij A en een gezochte waarde b. Neem een waarde a uit A, halverwege de lengte van de rij. Als b kleiner is dan a moeten we b in het linkerdeel van A zoeken, anders in het rechterdeel. Dat deel behandelen we dan weer net zoals A en zo verder tot we b gevonden hebben (of, als b niet in A voorkomt, een getal dat daar zo dicht mogelijk bij in de buurt ligt).
[bewerk] C-programmacode
Het volgende fragment van een C++-programma implementeert een bisectie-algoritme:
bool ArrayList::find(
char* sFind, // gezochte string
char** aStr, // verzameling strings waarin te zoeken
int nNItems, // aantal strings in de verzameling
int* piInsert // te retourneren invoegpositie
){
/* Deze methode gebruikt bisectie: deelt het te doorzoeken stuk
* steeds in tweeen en beoordeelt steeds een zijde
* van het nieuwe snijvlak. */
int iL= 0;
int iR= nNItems;
int nSpan= iR -iL;
bool bSearch= (nSpan > 0);
int iN= iL +nSpan/2;
bool bFound= false;
while (bSearch){
char* sN= aStr[iN];
int nCmp= strcmp(sFind,sN);
if (nCmp > 0){
/* gezochte string zit in of net rechts naast het rechter stuk */
iL= iN;
} else if (nCmp < 0){
/* gezochte string zit in of net links naast het linker stuk */
iR= iN;
} else{
bFound= true;
break;
}
if (nSpan==1){
if (nCmp > 0){
iN= iR;
} else{
iN= iL;
}
break; // niet gevonden; invoegpositie wel
}
nSpan= iR -iL;
iN= iL +nSpan/2;
} // einde zoeklus
*piInsert= iN; // invoegpositie of positie van de gevonden string
return bFound; // indien false: iN is de invoegpositie, anders de positie van de gevonden string
}
[bewerk] Toepassing op wiskundige functies
Laat 
een monotoon stijgende functie zijn. Stel nu dat we geïnteresseerd zijn in de waarde van x bij een gegeven f(x) = a. Dan kunnen we bisectie gebruiken om x te benaderen.
Het bovenstaande programmafragment zou als voorbeeld kunnen dienen, met de volgende aantekeningen:
char* sFind: de gegeven waarde a;char** aStr: het functievoorschrift;int nNItems:iLeniR, een schatting van het gebied waar x ligt, als drijvende-komagetallen;- char* sN= aStr[iN]: berekening van een functiewaarde voor een benadering van x;
if (nSpan==1): test of de gewenste nauwkeurigheid is gehaald.
De 'invoegpositie' is nu de benadering, met een fout ter grootte van (iR - iL).
[bewerk] Doelmatigheid
Bij het benaderen van een functiewaarde wordt de fout bij elke stap de helft kleiner, dat wil zeggen dat we één decimaal verkrijgen per (ruim) drie cycli (drie decimalen per 10 cycli). Bij toepassing op discrete waarden kunnen we 1.000 getallen doorzoeken in 10 cycli, 1.000.000 in 20 enzovoorts. Het aantal stappen tot de gewenste nauwkeurigheid is met bisectie van tevoren bekend.
Alhoewel bisectie betrouwbaar en eenvoudig is, zijn er methoden die in veel gevallen beter werken, vooral voor de toepassing op wiskundige functies. Zulke methodes maken gebruik van (een schatting van) de richtingscoëfficiënt op of rond het laatst gevonden punt. Bij functies zonder sprongen en knikken wijst die waarde ongeveer in de richting van het gezochte punt, zodat de volgende benadering gemiddeld genomen beter is dan met bisectie het geval zou zijn geweest. Voorbeelden zijn de methode van Newton-Raphson en Regula Falsi.
