Bouw zelf — vergelijk lineair en binair

Leerdoel: je zet beide algoritmes naast elkaar op dezelfde data en telt het werk. De theorie wordt nu meetbaar.

Opdracht

Schrijf beide algoritmes zo dat ze het aantal vergelijkingen tellen. De startcode laat ze los op gesorteerde lijsten van 10 tot 100.000 getallen, in het slechtste geval: het doel komt niet voor.

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

print(lineair_tellen(list(range(1000)), -1))   # 1000
print(binair_tellen(list(range(1000)), -1))    # 9

Wat zie je?

Interpretatie

n        lineair    binair
10       10         3
100      100        6
1000     1000       9
10000    10000      13
100000   100000     16

• Lineair: tien keer zo'n lange lijst kost tien keer zoveel werk. Het groeit even hard als n.
• Binair: tien keer zo'n lange lijst kost drie of vier vergelijkingen extra. Elke vergelijking halveert wat er nog over is, dus het werk groeit met het aantal keer dat je n kunt halveren.

Op een lijst van een miljard zou het verschil nog groter zijn: een miljard vergelijkingen tegenover ongeveer 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.

• binair_zoek_eerste([1, 2, 2, 2, 3], 2) → 1
• binair_zoek_eerste([1, 2, 2, 2, 3], 4) → -1

Tip

Bewaar een match in een variabele gevonden in plaats van meteen te returnen, en verklein daarna het zoekgebied naar links met hoog = midden - 1. Elke nieuwe match links van de vorige overschrijft gevonden. Als de lus stopt, staat daar de eerste.

Antwoord

def binair_zoek_eerste(lijst, doel):
    laag = 0
    hoog = len(lijst) - 1
    gevonden = -1
    while laag <= hoog:
        midden = (laag + hoog) // 2
        if lijst[midden] == doel:
            gevonden = midden
            hoog = midden - 1      # blijf links zoeken
        elif lijst[midden] < doel:
            laag = midden + 1
        else:
            hoog = midden - 1
    return gevonden

print(binair_zoek_eerste([1, 2, 2, 2, 3], 2))   # 1
print(binair_zoek_eerste([1, 2, 2, 2, 3], 4))   # -1

De lus stopt nog steeds gegarandeerd: ook bij een match krimpt het zoekgebied, want hoog gaat omlaag.

Door naar veelgemaakte fouten.