Binair zoeken uitgelegd: van lineair zoeken naar O(log n)

Zoeken in een lijst klinkt triviaal: loop alles af tot je het vindt. Dat werkt, maar bij een miljoen elementen kost het in het slechtste geval een miljoen vergelijkingen. Is de lijst gesorteerd, dan kan het met twintig. Dat is het verschil tussen lineair en binair zoeken.

Binair zoeken (binary search) is een van de meest gevraagde algoritmes op tentamens en in sollicitatiegesprekken, juist omdat het er simpel uitziet en toch vol zit met kleine valkuilen: < of <=, mid of mid+1? Op deze pagina zie je precies welke variant we gebruiken en waarom die klopt.

Lineair zoeken

Lineair zoeken (linear search) bekijkt de elementen één voor één, van voor naar achter, tot het gezochte element gevonden is of de lijst op is.

def lineair_zoeken(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i  # gevonden op index i
    return -1  # niet gevonden

static int lineairZoeken(int[] a, int x) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == x) {
            return i; // gevonden op index i
        }
    }
    return -1; // niet gevonden
}

Het voordeel: de lijst hoeft niet gesorteerd te zijn, en het werkt ook op een gelinkte lijst. Het nadeel: O(n). Staat het element achteraan of helemaal niet in de lijst, dan bekijk je alles.

Binair zoeken: het idee

Denk aan een woordenboek. Je zoekt "kwartel" en slaat het boek ergens in het midden open bij "mango". Omdat de woorden alfabetisch staan, weet je meteen: het moet in de eerste helft zitten. De tweede helft hoef je nooit meer te bekijken.

Binair zoeken doet hetzelfde met een gesorteerde array. Je houdt twee grenzen bij, lo en hi, waartussen het element moet zitten als het er is. Elke stap:

1. Bereken mid = ⌊(lo + hi) / 2⌋ (naar beneden afronden).
2. Is a[mid] gelijk aan x? Gevonden.
3. Is a[mid] < x? Dan zit x rechts van mid: lo = mid + 1.
4. Anders zit x links van mid: hi = mid - 1.

Je begint met lo = 0 en hi = n - 1, en je stopt als lo > hi: dan is het zoekgebied leeg en staat x niet in de array.

Uitgewerkt voorbeeld: gevonden

We zoeken x = 30 in deze array van tien elementen:

De waarden die achtereenvolgens worden vergeleken zijn 21, 34, 25, 30. Let op stap 3: (5 + 6) / 2 = 5,5, afgerond naar beneden geeft mid = 5.

Uitgewerkt voorbeeld: niet gevonden

Nu zoeken we x = 10 in dezelfde array:

Vergeleken waarden: 8 en 12 liggen naast elkaar en 10 zit ertussen. Na drie vergelijkingen (21, 8, 12) is het zoekgebied leeg. De eindwaarde van lo (hier 2) is precies de plek waar je 10 zou moeten invoegen om de array gesorteerd te houden; dat is handig om te onthouden.

De code

def binair_zoeken(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:  # zolang het zoekgebied niet leeg is
        mid = (lo + hi) // 2  # naar beneden afronden
        if a[mid] == x:
            return mid
        elif a[mid] < x:
            lo = mid + 1  # x zit rechts van mid
        else:
            hi = mid - 1  # x zit links van mid
    return -1  # niet gevonden

static int binairZoeken(int[] a, int x) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) { // zolang het zoekgebied niet leeg is
        int mid = lo + (hi - lo) / 2; // gelijk aan ⌊(lo+hi)/2⌋, maar zonder overflow
        if (a[mid] == x) {
            return mid;
        } else if (a[mid] < x) {
            lo = mid + 1; // x zit rechts van mid
        } else {
            hi = mid - 1; // x zit links van mid
        }
    }
    return -1; // niet gevonden
}

In Java schrijven we lo + (hi - lo) / 2 in plaats van (lo + hi) / 2. Voor niet-negatieve lo en hi levert dat dezelfde mid op, maar het voorkomt dat lo + hi groter wordt dan de maximale int bij hele grote arrays. In Python bestaat dat probleem niet.

Off-by-one-valkuilen

Binair zoeken is berucht om fouten van één positie. De drie keuzes in onze variant horen bij elkaar:

Wat gaat er mis als je een van de drie verandert?

• while lo < hi: in het eerste voorbeeld stop je na stap 3 met lo = hi = 6, zonder a[6] te bekijken. Je meldt "niet gevonden" terwijl 30 er wel staat.
• lo = mid in plaats van mid + 1: met lo = 5, hi = 6 krijg je mid = 5, en als a[5] < x blijft lo op 5 staan. Het zoekgebied krimpt niet: een oneindige lus.
• hi = n met <=: dan kan mid gelijk worden aan n en lees je buiten de array.

Er bestaan ook correcte varianten met hi = n (exclusief) en while lo < hi. Die werken prima, maar meng de twee stijlen nooit. Op Practicely gebruiken we altijd de variant hierboven.

Variant: het eerste voorkomen

Staat x meerdere keren in de array, dan geeft gewoon binair zoeken een willekeurige van de voorkomens terug. In [1, 3, 3, 3, 3, 7, 9] vindt het 3 al bij de eerste stap, op index 3. Wil je het eerste voorkomen, dan ga je na een treffer verder zoeken in de linkerhelft en onthoud je de beste index tot nu toe:

Daarna is lo > hi en is het antwoord index 1.

def eerste_voorkomen(a, x):
    lo, hi = 0, len(a) - 1
    antwoord = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            antwoord = mid  # onthouden en links verder zoeken
            hi = mid - 1
        elif a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return antwoord

static int eersteVoorkomen(int[] a, int x) {
    int lo = 0, hi = a.length - 1;
    int antwoord = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) {
            antwoord = mid; // onthouden en links verder zoeken
            hi = mid - 1;
        } else if (a[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return antwoord;
}

Het laatste voorkomen werkt spiegelbeeldig: na een treffer lo = mid + 1. Met eerste en laatste voorkomen samen tel je in O(log n) hoe vaak een waarde voorkomt.

Complexiteit

Elke stap halveert het zoekgebied. Na k stappen zijn er hooguit n / 2ᵏ kandidaten over, dus na ongeveer log₂ n stappen is er nog één. Als recurrente betrekking: T(n) = T(n/2) + 1, en volgens de mastermethode (zie complexiteit) is dat O(log n).

Moet je maar één keer zoeken in ongesorteerde data, dan is lineair zoeken sneller dan eerst sorteren (O(n log n)) en dan binair zoeken. Zoek je vaak in dezelfde data, dan verdient het sorteren zich snel terug. Nog sneller opzoeken kan met een hashtabel, en voor data die steeds verandert is een binaire zoekboom handig.

Veelgemaakte fouten op het tentamen

1. Binair zoeken op een ongesorteerde array. Het algoritme geeft dan gewoon een fout antwoord, zonder foutmelding. Controleer altijd eerst de voorwaarde.
2. mid naar boven afronden. (5 + 6) / 2 wordt 5, niet 6. Bij een traceervraag verschuift één verkeerde mid alle volgende stappen.
3. while lo < hi gebruiken bij de inclusieve variant, waardoor je het laatste kandidaat-element nooit bekijkt.
4. lo = mid of hi = mid schrijven in plaats van mid + 1 en mid - 1. Dat kan een oneindige lus opleveren.
5. Bij de traceervraag de laatste vergelijking vergeten. Ook de vergelijking waarin x gevonden wordt, hoort in de lijst van vergeleken waarden.

Samenvatting

• Lineair zoeken werkt altijd en kost O(n); binair zoeken eist een gesorteerde array en kost O(log n).
• Onze variant: lo = 0, hi = n - 1, mid = ⌊(lo + hi) / 2⌋, while lo <= hi.
• Bij a[mid] < x wordt lo = mid + 1, anders hi = mid - 1; zo krimpt het zoekgebied altijd.
• Voor het eerste voorkomen zoek je na een treffer links verder en onthoud je de index.