Hur fungerar binär sökning och vad kräver den?

Question

Accepted Answer

**Binär sökning** hittar ett mål i en **sorterad** array genom att upprepade gånger halvera sökintervallet. Varje jämförelse eliminerar hälften av de återstående elementen, vilket ger **O(log n)** tid. ## Idén Titta på mittelelementet. Om det är lika med målvärdet, klart. Om målvärdet är mindre, sök i vänster halva; om större, sök i höger halva. Upprepa tills värdet hittas eller intervallet är tomt. ## Exempel ```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 ``` ## Spårning ```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 ``` ## Komplexitet - **Tid:** O(log n). **Minne:** O(1) iterativ. ## Fallgropar **Inmatningen måste vara sorterad** — annars är resultaten meningslösa. Var försiktig med off-by-one-fel i `lo`/`hi` och heltalsöverflöde i vissa språk (använd `lo + (hi-lo)//2`). ## Varför det är viktigt Halvering av sökutrymmet förvandlar ett miljonelement-sökning till ~20 jämförelser. Dela-och-härska-mönstret bakom det dök upp igen i träd, databaser och otaliga intervjuproblem. Att veta dess enda hårda krav — sorterad inmatning — håller dig ifrån ett klassiskt subtilt fel.