Ga naar hoofdinhoud

Cheatsheet — lineair zoeken

Snelle referentie. Klap open wat je nodig hebt.

Het algoritme zelf​

De canonieke implementatie
def zoek(lijst, doel):
    for i, waarde in enumerate(lijst):
        if waarde == doel:
            return i
    return -1
Variant met range
def zoek(lijst, doel):
    for i in range(len(lijst)):
        if lijst[i] == doel:
            return i
    return -1

De bouwstenen​

1. Door een lijst lopen
for waarde in lijst:                  # alleen waarden
    ...

for i, waarde in enumerate(lijst):    # index + waarde
    ...

for i in range(len(lijst)):           # alleen index
    ...
2. Vergelijken
  • == → vergelijking (if x == 5)
  • != → ongelijk (if x != 5)
  • <, >, <=, >= → andere vergelijkingen
3. Functie + return
def naam(parameter1, parameter2):
    ...
    return iets         # stopt de functie en geeft 'iets' terug

return stopt de functie direct — code erna wordt niet meer uitgevoerd.

4. Toevoegen aan een lijst
resultaat = []
resultaat.append(42)        # achteraan toevoegen

Eigenschappen​

Wanneer werkt het?
  • Op elke lijst — gesorteerd of niet.
  • Op lijsten van strings, getallen, of wat dan ook, zolang == betekenis heeft.
Hoe snel is het?
  • Beste geval: doel staat vooraan → 1 vergelijking.
  • Slechtste geval: doel staat achteraan of bestaat niet → n vergelijkingen.
  • We zeggen: O(n) (lineair in de lengte).
Conventie voor "niet gevonden"
  • -1 — duidelijk geen geldige index.
  • Of None — Python-stijl.
  • Of raise ValueError(...) — als je écht wil dat de aanroeper het merkt.

Veelgemaakte fouten (snel)​

Top-3 fouten
  1. return -1 binnen de for-lus → returnt na 1 iteratie.
  2. = waar je == bedoelt → SyntaxError of stille bug.
  3. range(len(lijst) + 1) → IndexError op de laatste iteratie.

Klaar met lineair zoeken? Probeer nu binair zoeken → en zie hoeveel sneller het kan op een gesorteerde lijst.