14. Binair zoeken
Binair zoeken is een efficiënte zoekmethode om een waarde te vinden in een gesorteerde lijst of array. In plaats van elk element één voor één te controleren (zoals bij lineair zoeken), halveert binair zoeken bij elke stap het zoekgebied. Hierdoor is het veel sneller, vooral bij grote datasets.
Hoe werkt binair zoeken?
Je begint met het hele gesorteerde lijst.
Je bekijkt het middelste element.
Als het middelste element gelijk is aan de gezochte waarde, ben je klaar.
Als de gezochte waarde kleiner is dan het middelste element, zoek je verder in het linkerdeel van de array.
Als de gezochte waarde groter is dan het middelste element, zoek je verder in het rechterdeel van de array.
Je herhaalt deze stappen totdat je het element vindt of totdat het zoekgebied leeg is.
Opdracht 14.1 Maak de beveropdracht Vind de schat
Stel je voor dat iemand een getal in gedachten heeft tussen 0 en 100, en je probeert dat getal te raden dan is binair zoeken een hele goede methode. Hier is hoe je dit zou doen met een "binair zoek"-strategie:
Begin met het hele bereik: 0 tot 100.
Kies het middelste getal: Het getal dat halverwege het huidige zoekgebied ligt. In het geval van 0 tot 100 kies je 50.
Vraag of het getal 50 is:
Als het gezochte getal 50 is, ben je klaar.
Als het gezochte getal lager is dan 50, richt je de zoektocht op het gebied van 0 tot 50.
Als het gezochte getal hoger is dan 50, richt je de zoektocht op het gebied van 50 tot 100.
Herhaal het proces:
Kies het nieuwe middelste getal van het resterende zoekgebied. Als je in het gebied 50 tot 100 zoekt, is het nieuwe middelpunt 75.
Vraag of het het getal is, en pas het zoekbereik opnieuw aan.
Blijf halveren:
Herhaal bovenstaande stappen totdat je het juiste getal hebt gevonden of het zoekgebied geen verdere mogelijkheden biedt.
De standaard code voor een binary search functie zou er zo uit kunnen zien, als we proberen een target T te vinden in array A.
int left = 0; //zet de linkergrens op 0
int right = A.size() - 1; //zet de rechtergrens op de grootte van de array
while (left <= right) {
int mid = left + (right - left) / 2; //bereken het midden
if (A[mid] < T) {
left = mid; //pas de linkergrens aan. Soms gebruik je mid - 1.
} else if (A[mid] > T) {
right = mid; //pas de rechtergrens aan. Soms gebruik je mid + 1.
} else {
return mid; // target is gevonden
}
}
return -1; // target is niet gevonden
Opdracht 14.2 Maak de opdracht: getal raden.
Opdracht 14.3 Maak de opdracht binair zoeken.
Opdracht 14.4 Maak de opdracht bussen.
Last updated