Hvordan fungerer binær søgning, og hvad kræver det?

Question

Accepted Answer

**Binær søgning** finder et mål i et **sorteret** array ved gentagne gange at halvere søgeintervallet. Hver sammenligning eliminerer halvdelen af de resterende elementer, hvilket giver **O(log n)** tid. ## Idéen Kig på det midterste element. Hvis det svarer til målet, er du færdig. Hvis målet er mindre, søger du i den venstre halvdel; hvis det er større, søger du i den højre halvdel. Gentag indtil det er fundet, eller intervallet er tomt. ## Eksempel ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## Sporning ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## Kompleksitet - **Tid:** O(log n). **Rum:** O(1) iterativ. ## Faldgruber **Inputtet skal være sorteret** — ellers er resultaterne meningsløse. Pas på off-by-one-fejl i `lo`/`hi` og heltalsoverløb i nogle sprog (brug `lo + (hi-lo)//2`). ## Hvorfor det betyder noget Halvering af søgerummet gør et opslag på en million elementer til ~20 sammenligninger. Dele-og-hersk-mønsteret bag det dukker op igen i træer, databaser og utallige interviewspørgsmål. At kende dens ene hårde krav — sorteret input — holder dig væk fra en klassisk subtil fejl.