Binärsökning
Hittar ett värde i en sorterad array genom att titta i mitten och kasta bort halvan där det inte kan finnas. Varje jämförelse halverar det som är kvar.
- bästa fall Ω(1)
- genomsnitt Θ(log n)
- värsta fall O(log n)
- minne O(1)
Vad betyder det här?
- Sorterad: i stigande ordning. Binärsökning kräver det; på osorterad data ger den fel svar.
- Halvering: varje jämförelse kastar bort hälften av det som är kvar, halvan där målet inte kan finnas.
- log₂ n: hur många gånger n kan halveras innan 1 är kvar. För 64 värden är det 6, alltså högst 7 jämförelser.
- mitt (mid)
- hittad
- utesluten
- mål
Varje mitt som sökningen kunde välja; en körning är en väg nedåt. Nivåer: 5 = ⌈log₂(24 + 1)⌉, flest jämförelser den kan behöva.
Letar efter 70 bland 24 sorterade värden: hela arrayen är fortfarande med.
Blanksteg: spela upp eller pausa. Vänster och höger pil: steg. Home och End: hoppa.
Prova det här: Välj ett mål som inte finns i arrayen. Sökningen slutar ändå efter högst ⌈log₂(n + 1)⌉ jämförelser, när lo passerar hi.
Så fungerar det
Binärsökning håller två markörer, lo och hi, runt den del av arrayen där målet fortfarande kan finnas. Den tittar på värdet i mitten: är det målet är den klar; är det mindre kan målet bara ligga till höger, så lo flyttas förbi mitten; är det större flyttas hi före. Varje steg halverar resten: 64 värden kräver högst 7 jämförelser och en miljon högst 20. När lo passerar hi finns inget kvar: värdet finns inte i arrayen.
När det är ett bra val
Använd binärsökning när datan är sorterad och du kan hoppa till vilken position som helst: ett ord i en sorterad lista, en version i en releasehistorik, git bisect, platsen att infoga på i en sorterad array. På osorterad data ger den fel svar, och att sortera först lönar sig bara om du söker många gånger.