Søgealgoritmer — lineær O(n), binær O(log n)

It A · STX · A-niveau · Datastrukturer og algoritmer

💻 Søgealgoritmer — lineær O(n), binær O(log n)

Søgealgoritmer = teknikker til at finde et bestemt element i en datasamling.

2 grundlæggende:

1.

Lineær søgning (linear search) — gå gennem element for element fra start.

Tidskompleksitet: O(n) — i værste tilfælde n sammenligninger.

Plads: O(1).

Implementation Python: def linear_search(arr, target): for i, x in enumerate(arr): if x == target: return i; return -1.

Hvornår: usorteret data, små data (n < ~50), simple lookup, søg i linked list.

Eksempel: find "Hassan" i navne-liste på 100 elever — gennemsnit 50 sammenligninger, worst 100.

2.

Binær søgning (binary search) — kræver SORTERET data. Princip: del søgeområde i 2 ved hver iteration.

Algoritme:

• (a) Sammenlign target med MIDTERSTE element.
• (b) Hvis lig → fundet.
• (c) Hvis target < midterste → søg i venstre halvdel.
• (d) Hvis target > midterste → søg i højre halvdel.
• (e) Gentag indtil fundet eller område tomt.

Tidskompleksitet: O(log n) — fordobles n: kun 1 ekstra iteration.

Plads: O(1) iterativ, O(log n) rekursiv (call-stack).

Implementation Python: ``def binary_search(arr, target):\n lo, hi = 0, len(arr) - 1\n while lo <= hi:\n mid = (lo + hi) // 2\n if arr[mid] == target: return mid\n elif arr[mid] < target: lo = mid + 1\n else: hi = mid - 1\n return -1``.

Sammenligning (n = 1.000.000): linear ~500.000 sammenligninger gennemsnit, binær ~20 sammenligninger.

Forskel: log₂(1.000.000) = 19,9.

Eksempel — telefonbog: at fin

Læringsmål

• Redegøre for forskellen mellem lineær og binær søgning
• Implementere binær søgning i et sorteret array
• Forklare hvorfor binær søgning kræver sorterede data

Sådan kan du arbejde med emnet

• Implementér binær søgning i Python og beregn, hvad der maksimalt er antallet af trin for 1000 elementer
• Forklar, hvad forudsætningen er for at bruge binær søgning
• Sammenlign lineær og binær søgning: hvornår er det bedre at bruge lineær søgning?

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