Het tweede algoritme van dit hoofdstuk lost een ander probleem op: een element terugvinden in een lijst. Net als quicksort en mergesort gebruikt het de techniek verdeel en heers. Het heet binair zoeken (Engels: binary search).

Binair zoeken is een efficiënt zoekalgoritme om een specifiek element te vinden in een gesorteerde array.

• Invoer: een gesorteerde lijst van elementen en een doelwaarde.
• Uitvoer: de index van het doelelement in de lijst, of -1 als het niet aanwezig is.

Merk op: binair zoeken werkt alleen op een gesorteerde lijst. Dat de lijst op volgorde staat, is net wat het algoritme zo snel maakt.

Het kaartspel

Stel je een rij kaarten voor, met de rug naar boven, op elke kaart een positief getal. De kaarten liggen van klein naar groot gerangschikt. Je krijgt een te zoeken waarde en je mag kaarten omdraaien om hun getal te zien. Hoe vind je de gezochte kaart met zo weinig mogelijk omdraaien?

Je zou alle kaarten één voor één van links naar rechts kunnen omdraaien tot je de juiste tegenkomt. Dat is brute force, en bij veel kaarten erg traag. Het kan veel slimmer:

• Draai de middelste kaart om.
• Omdat de kaarten van klein naar groot liggen, weet je meteen of de gezochte kaart links of rechts van het midden ligt: is het getal op de middelste kaart te groot, dan ligt de gezochte kaart links; is het te klein, dan rechts.
• De andere helft mag je voortaan negeren. Kies opnieuw (ongeveer) het midden van het overgebleven gebied, en draai die kaart om.
• Ga zo verder tot je de kaart vindt.

Bij elke stap halveer je het aantal kaarten dat nog overblijft. Dat is precies verdeel en heers: je splitst het probleem (de hele rij doorzoeken) telkens in twee en je houdt maar één helft over.

In hoeveel stappen?

Hoe snel is dat halveren nu eigenlijk? Bekijk eens hoeveel kaarten je in het slechtste geval moet omdraaien:

• 13 kaarten: elke kaart vind je in hoogstens 4 stappen.
• 27 kaarten: na één keer halveren blijven er ongeveer 13 over, het vorige geval. Je hebt dus hoogstens één stap meer nodig: 4 + 1 = 5 stappen.
• 100 kaarten: na één stap blijven er 50 over, na twee stappen 25. Vanaf 25 zit je in de buurt van het 27-geval (5 stappen), dus 5 + 2 = 7 stappen volstaan.

Zie je het patroon? Telkens je het aantal kaarten verdubbelt, komt er maar één stap bij. Honderd kaarten doorzoeken kost 7 stappen, duizend kaarten ongeveer 10, een miljoen ongeveer 20. Met brute force (kaart per kaart) zou je in het slechtste geval alle kaarten moeten omdraaien, dus 100, 1000 of een miljoen.

Binair zoeken is zo performant omdat het bij elke stap de zoekruimte halveert. Het aantal stappen groeit logaritmisch met het aantal elementen.

In code

We passen dit toe op een gesorteerde array lijst van gehele getallen. We houden twee grenzen bij, links en rechts, die het stuk afbakenen waarin de gezochte waarde nog kan liggen. Het midden bereken je met een gehele deling. We geven de index terug, of -1 als het getal niet in de lijst zit.

// geef de index terug van het gegeven getal in de lijst,
// of -1 als het niet in de lijst zit
int IndexInLijst(int[] lijst, int getal)
{
    int links = 0;
    int rechts = lijst.Length;
    int gevonden = -1;

    while (links < rechts && gevonden == -1)
    {
        int midden = (links + rechts) / 2;   // gehele deling!

        if (getal == lijst[midden])
        {
            gevonden = midden;                // gevonden op deze index
        }
        else if (getal < lijst[midden])
        {
            rechts = midden;                  // zoek verder in de linkerhelft
        }
        else
        {
            links = midden + 1;               // zoek verder in de rechterhelft
        }
    }

    return gevonden;
}

Twee details die makkelijk fout lopen:

• bij de linkerhelft zet je rechts = midden (en dus niet midden - 1), anders kan je het laatste kandidaat-element missen;
• bij de rechterhelft zet je links = midden + 1. Het + 1 is hier essentieel: zonder dat zou de lus blijven hangen in een oneindige lus wanneer het getal niet in de lijst zit.

De stopvoorwaarde links < rechts zorgt dat de lus stopt zodra het zoekgebied leeg is. Dan is gevonden nog altijd -1 en weet je dat het getal er niet in zit.

In de volgende oefening schrijf je deze functie zelf en gebruik je ze om in een gesorteerde lijst te zoeken.