Bouw zelf — vergelijk lineair en binair

Leerdoel: je zet beide algoritmes naast elkaar op dezelfde data en visualiseert het verschil. Theorie wordt nu zichtbaar.

Opdracht

Schrijf beide algoritmes zó dat ze het aantal vergelijkingen tellen. Vergelijk dan op een reeks lijstgroottes en plot een grafiek.

Python

Code-omgeving wordt voorbereid…

Tip

Voor lineair_tellen: doorloop de lijst, hoog elke ronde een teller op, returnt aan het eind die teller — ook als je niets vond.

Voor binair_tellen: kopieer binair_zoek en vervang de return midden en return -1 door return vergelijkingen. Hoog vergelijkingen op binnen de while-lus.

Antwoord

def lineair_tellen(lijst, doel):
    vergelijkingen = 0
    for waarde in lijst:
        vergelijkingen += 1
        if waarde == doel:
            return vergelijkingen
    return vergelijkingen

def binair_tellen(lijst, doel):
    laag = 0
    hoog = len(lijst) - 1
    vergelijkingen = 0
    while laag <= hoog:
        vergelijkingen += 1
        midden = (laag + hoog) // 2
        if lijst[midden] == doel:
            return vergelijkingen
        elif lijst[midden] < doel:
            laag = midden + 1
        else:
            hoog = midden - 1
    return vergelijkingen

Wat zie je in de grafiek?

Interpretatie

Op log-log-assen (zowel x als y logaritmisch) zie je:

• Lineair: een rechte lijn met helling 1 → werk groeit lineair in n.
• Binair: een rechte, veel platter lijn → werk groeit logaritmisch in n.

Voor n = 100.000:

• Lineair: 100.000 vergelijkingen
• Binair: ~17 vergelijkingen

Op een lijst van een miljard zou het verschil nog dramatischer zijn: 1 miljard versus ~30.

Uitdaging (optioneel)

Pas binair zoeken aan zodat het bij duplicaten de eerste voorkomende index returnt. Hint: stop niet bij de eerste match — blijf doorzoeken in de linker helft.

Door naar stap 11: veelgemaakte fouten →