WisFaq!

Binair zoeken

Hallo!
Kunnen jullie mij vertellen wat het verschil is tussen binair zoeken en de bisectiemethode? Wikipedia zegt: De bisectiemethode vertoont overeenkomsten met binair zoeken binnen een geordende rij gegevens.
Ik snap het niet helemaal... Kunnen jullie het verduidelijken aub?
Dankjewel!!

Lisa
24-10-2015

Antwoord

Hallo Lisa,

Binair zoeken is een manier om binnen een gesorteerde rij getallen op te zoeken waar een bepaald getal staat. Neem bijvoorbeeld deze rij van 23 getallen:

getal:  1  2  4  5  7  8 11 15 18 19 21 23 24 26 30 32 33 35 38 40 41 45 46
nummer: 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

en je zou willen weten waar het getal 11 staat. Dan bekijk je eerst wat het middelste getal is. In dit geval is dit 23. Omdat 23 groter is dan 11, weet je dat het gezochte getal in de eerste helft zit, dus in deze groep:

getal:  1  2  4  5  7  8 11 15 18 19 21
nummer: 1  2  3  4  5  6  7  8  9 10 11

Nu bekijk je van deze groep weer het middelste getal, dit is 8. Omdat het gezochte getal (11) groter is dan 8, weet je dat je in de rechter helft van deze groep moet kijken:

getal:  11 15 18 19 21 
nummer:  7  8  9 10 11

Je kijkt opnieuw naar het middelste getal van de overgebleven groep. Dit is 18, dus je moet weer in de linker helft kijken:

getal:  11 15 
nummer:  7  8

Nu hoef je alleen nog getal nr. 7 en nr. 8 te bekijken om te zien dat het gezochte getal op nummer 7 staat. In totaal heb je hoogstens 5 getallen moeten bekijken in plaats van de hele rij. Vooral bij lange rijen gaat dit sneller dan alle getallen bekijken.

Met de bisectiemethode kan je bijvoorbeeld benaderen hoe groot √2 is. Stel x=√2, dan is x²=2. We zoeken dus een getal x waarvoor geldt: x²=2.

Dit getal moet tussen 1 en 2 liggen, want 1²=1 (dus 1 is te klein) en 2²=4 (dus 2 is te groot). Dus proberen we een getal dat hier precies tussenin ligt:

x=1,5.
We berekenen: x²=2,25. Dit is te groot, dus x ligt tussen 1 en 1,5. We proberen dan weer en getal dat hier precies tussenin ligt:

x=1,25
We berekenen: x²=1,5625. Dit is te klein, dus x ligt tussen 1,25 en 1,5. We proberen weer en getal dat hier precies tussenin ligt: x=1,375

enz. enz.

De overeenkomst tussen binair zoeken en de bisectiemethode is dus dat we het 'zoekgebied' steeds in twee stukken delen, en bekijken in welk van de twee helften we verder moeten zoeken.
Bij binair zoeken hoeven we niets te berekenen, we bekijken steeds of we het gezochte element hebben gevonden of niet. Uiteindelijk weten we op welke plaats in de rij het gezochte element staat.
Bij de bisectiemethode komen we steeds dichter bij de juiste waarde van een onbekend getal.

GHvD
25-10-2015