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

Kommunikation og IT A · HTX · A-niveau · Datastrukturer og algoritmer

💻 Søgealgoritmer

Lineær søgning — gennemgår listen element for element:

```python

def lineær_søgning(liste, mål):

for i, x in enumerate(liste):

if x == mål:

return i

return -1 # ikke fundet

```

Kompleksitet: O(n). Virker på usorteret data.

Binær søgning — halverer søgerum ved hvert trin:

```python

def binær_søgning(liste, mål):

venstre, højre = 0, len(liste) - 1

while venstre <= højre:

midt = (venstre + højre) // 2

if liste[midt] == mål:

return midt

elif liste[midt] < mål:

venstre = midt + 1

else:

højre = midt - 1

return -1

```

Kompleksitet: O(log n). Kræver sorteret data.

Eksempel: Søg i 1.000.000 elementer → lineær: 500.000 sammenligninger. Binær: 20 sammenligninger.

Python: bisect-modulet har binær søgning built-in.

Læringsmål

• Implementere lineær og binær søgning fra bunden
• Forklare kompleksitetsforskellen O(n) vs. O(log n)
• Afgøre hvornår binær søgning er anvendelig
• Bruge Pythons bisect-modul til effektiv søgning

Sådan kan du arbejde med emnet

• Implementer binær søgning i et sorteret array og find indekset for tallet 42
• Forklar hvorfor binær søgning kræver et sorteret array
• Beregn det maksimale antal sammenligninger ved binær søgning i et array med 1000 elementer

Træningsforslag

• Mål tidsforskellen for lineær vs. binær søgning på 1 million elementer
• Implementér binær søgning rekursivt
• Løs LeetCode #704 (Binary Search)