Zoeken komt in veel toepassingen voor, bijvoorbeeld het zoeken van het nulpunt van een functie, of als onderdeel van “opslaan en terugzoeken”.
De twee belangrijkste basisalgoritmen om te zoeken zijn lineair zoeken en binair zoeken. We behandelen deze aan de hand van het raden van een getal: dat kun je ook als een zoekprobleem beschouwen.
Voor binair zoeken heb je veel minder stappen nodig dan voor lineair zoeken, maar binair zoeken is alleen mogelijk als de “zoekruimte” handig georganiseerd is, bijvoorbeeld als een alfabetische lijst van namen.
Merk op dat we bij het zoeken alleen de vorm gebruiken, bijvoorbeeld namen of getallen. De betekenis van deze namen of getallen speelt hierbij geen rol.
Bij het opslaan en terugzoeken van gegevens gebruik je meestal een deel van de gegevens als zoeksleutel (key); bijvoorbeeld om het telefoonnummer en het e-mailadres van één van je contacten te zoeken, gebruik je de naam als zoeksleutel.
Als deze zoeksleutels handig georganiseerd zijn, bijvoorbeeld als alfabetische lijst, dan kun je de andere gegevens daarmee efficiënt terugzoeken.
Raad een getal
We proberen een slimme oplossing te vinden voor het probleem om een getal te raden, bijvoorbeeld tussen 0 en 99 (“tot honderd”).
Lineair zoeken
Een simpele manier is om de getallen één voor één te proberen: is het 0? is het 1? enz.
Dit is niet erg efficiënt: je hebt in het ergste geval 100 vragen nodig, en gemiddeld nog altijd 50 vragen.
Deze aanpak, “lineair zoeken”, is wel effectief: je weet zeker dat je het gezochte getal vindt.
Als je geen betere aanpak kunt vinden, kun je daarom altijd terugvallen op lineair zoeken.
Binair zoeken
Als je mag vragen of het te raden getal groter of kleiner is dan een getal dat je noemt, dan kun je met veel minder vragen toe.
Je halveert dan in elke stap het gebied waarin het gezochte getal kan liggen. Vanwege dit halveren heet deze aanpak “binair zoeken”.
We kunnen deze aanpak het best uitleggen aan de hand van de getallenlijn, met daarop de getallen 0..100, en twee blokjes.
Het linkerblokje lo leg je bij het getal 0, het rechterblokje hi bij het getal 100. Het gezochte getal x ligt nu tussen deze twee blokjes: lo≤x<hilo≤x<hi. Als hi=lo+1hi=lo+1 - de blokjes liggen tegen elkaar aan, zijn we klaar: lo is het gezochte getal, immers lo≤x<lo+1lo≤x<lo+1.
We onderzoeken steeds het getal in het midden tussen lo en hi: m=lo+hi/2m=lo+hi/2. (We gebruiken hier de deling voor gehele getallen: 99/2 = 49. Dit heet ook wel het quotient.)
Als m groter is dan het gezochte getal, dan verplaatsen we hi naar m. In het andere geval verplaatsen we lo naar m.
Merk op dat nu blijft gelden dat lo≤x<hilo≤x<hi. Het gezochte getal ligt tussen de twee blokjes. Dit noemen we daarom wel de invariant van dit algoritme.
We kunnen deze aanpak beschrijven in een spreadsheet, op de volgende manier:
In een spreadsheet ziet dit er zo uit:
A | B | C | D | |
---|---|---|---|---|
1 | n | lo | m | hi |
2 | 0 | 0 | =QUOTIENT(B2+D2,2) | 100 |
3 | 1 | =IF(x < C2, B2, C2) | =QUOTIENT(B3+D3,2) | =IF(x < C2, C2, D2) |
4 | 2 | =IF(x < C3, B3, C3) | =QUOTIENT(B4+D4,2) | =IF(x < C3, C3, D3) |
... | ... | ... | ... | ... |
De spreadsheet met dit voorbeeld (zoeken-en-sorteren) vind je onder Bijlagen
Deze aanpak van het raden van een getal kunnen we gebruiken bij het zoeken naar een waarde in geordende reeks.
Enkele voorbeelden: het zoeken in een woordenboek of in een geordende lijst van namen. (Het zoeken van een naam in een telefoonboek zal niet meer tot de verbeelding spreken.)
Omdat deze aanpak van het zoekprobleem zo efficiënt is, is sorteren ook belangrijk: we zorgen ervoor dat reeksen waarden waarin we moeten zoeken, geordend zijn, zodat we efficiënt kunnen zoeken.