Lineær og binær søgning

Informatik C · STX · C-niveau · Computational thinking

💻 Lineær og binær søgning

Lineær søgning (sequential search): tjek hvert element i listen til match findes.

Tidskompleksitet: O(n).

Pseudokode: ``\nFOR hver element i liste:\n IF element == mål: RETURN index\nRETURN -1\n`` Virker på enhver liste — sorteret eller ej.

Binær søgning (binary search): kun for sorterede lister! Tjek midten, halvdelen kasseres hver gang.

Tidskompleksitet: O(log n) — meget hurtigere.

Pseudokode: ``\nlav, høj = 0, n-1\nWHILE lav <= høj:\n mid = (lav+høj)//2\n IF liste[mid] == mål: RETURN mid\n ELIF liste[mid] < mål: lav = mid+1\n ELSE: høj = mid-1\nRETURN -1\n`` Eksempel: søge i ordbog med 100.000 ord. Lineær: op til 100.000 sammenligninger. Binær: max 17 (log₂ 100000 ≈ 16,6).

Forudsætning: sorteret liste — hvis usorteret, koster sorteringen O(n log n) — kun værd hvis flere søgninger.

Anvendelser: datalager-indekser, telefonbog, autocomplete, IP-routing. Hash-baseret søgning O(1) i hash-tabel — endnu hurtigere men kræver ekstra hukommelse.

Læringsmål

• Anvende dekomposition (opdele problemer)
• Identificere mønstergenkendelse og abstraktion
• Skrive pseudokode og flowcharts
• Anvende lineær og binær søgning
• Anvende sortering (boble, indsættelse)

Sådan kan du arbejde med emnet

• Implementér lineær og binær søgning i Python og test, hvor mange trin det tager at finde et element i en sorteret liste med 100 elementer
• Forklar, hvad der er forudsætningen for at bruge binær søgning
• Beregn, hvad det maksimale antal trin i binær søgning er for en liste med 1024 elementer

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.