# Bisectie

Bisectie, uit het Latijn: 'in tweeën snijden', of binair zoeken is een methode om in een rij een element te vinden dat aan een bepaald criterium moet voldoen, door de af te zoeken aaneengesloten deelrij van mogelijke waarden steeds te halveren.
De methode werkt alleen als snel kan worden vastgesteld of het gezochte element zich in de ene helft of in de andere helft van de nog mogelijke waarden bevindt. Dat betekent in de praktijk dat de rij geordend moet zijn.

## Voorbeeld

Gezocht wordt waar in de geordendede getallenrij $a_{0}<a_{1}<\ldots <a_{8}<a_{9}$ zich het element 7 bevindt. Vergelijk het element $a_{5}=13$ ongeveer halverwege de rij met 7. Aangezien 7 kleiner is dan 13 moet 7 in het linkerdeel van de rij gezocht worden, anders in het rechterdeel. Uit het linkerdeel wordt het element halverwege, $a_{2}=5$, weer vergeleken met 7. Omdat 5 kleiner is dan 7, ligt 7 dus kennelijk rechts van 7, dus bij $a_{3}$ en $a_{4}$. Vergelijk $a_{4}$ nog met 7. $a_{4}=11$, dus ligt 7 links van $a_{4}$ en is $a_{3}=7$.
Binair zoeken is de gebruikelijke manier om iets in een woordenboek op te zoeken. Men opent het boek ongeveer in het midden en ziet dan of het gezochte woord in de eerste of tweede helft van het boek moet worden gezocht. In die helft wordt verder gezocht. In de praktijk weet men meteen al ongeveer in welk deel van het boek moet worden gezocht: begint het gezochte woord met een A, dan begint men niet in het midden van het boek. Dat maakt de procedure nog efficiënter.

## Implementatie in C++
### Recursief

Het volgende fragment van een C++-programma implementeert een recursief bisectie-algoritme:

### Lineair

Het volgende fragment implementeert een lineair bisectie-algoritme:

## Toepassing op wiskundige functies

Laat $x\rightarrow f(x)$ een monotoon stijgende functie zijn. Om de waarde van $x$ bij een gegeven $f(x)=a$ te vinden is nu bisectie te 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: iL en iR, een schatting van het gebied waar x ligt, als drijvende-kommagetallen;
* 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).

## 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 zijn 1000 getallen te doorzoeken in 10 cycli, 1.000.000 in 20 enzovoorts. Het aantal stappen tot de gewenste nauwkeurigheid is met bisectie van tevoren bekend. De worst-case-complexiteitsgraad van de bisectie is logaritmisch, $O(log\,n)$ in grote-O-notatie.
Hoewel 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 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 de regula falsi.