Binärsökning

Binärsökning

Sökalgoritm, söndra-och-härska-algoritm

Binärsökningsträd med 9 noder och höjden 4.

Binärsökning är en algoritm för att avgöra om en mängd innehåller ett givet element. Sökningen utförs i flera steg och i varje steg skall man utesluta att halva den kvarvarande mängden innehåller elementet och därmed kunna koncentrera sig på den andra halvan.

Intervallhalveringsmetoden är en term som används om både binärsökning och den matematiska problemlösningsmetoden i Bolzanos sats.

Ett exempel på binärsökning är uppslagning av ett ord eller namn i en alfabetiskt ordnad lista, till exempel en tryckt telefonkatalog eller en ordbok. Man börjar med att titta i mitten av listan. Genom att jämföra det sökta ordet med det som står i mitten av listan, vet man vilken halva av listan man ska fortsätta med. Efter andra uppslagningen återstår bara en fjärdedel av listan.

Om hela listan har N uppslagsord, krävs högst $\lceil \log _{2}N\rceil$ uppslagningar eller halveringar för att hitta rätt ställe, eller 2-logaritmen avrundad uppåt.

Antal noder $N$	2-logaritmen $\log _{2}N$	avrundad uppåt $\lceil \log _{2}N\rceil$	Kommentar
9	3,17	4	Grafen i bilden här intill har 9 noder och höjden 4.
900	9,81	10
1 953 033	20.8	21	Alla artiklar i svenskspråkiga Wikipedia (januari 2015).
9 miljoner	23,1	24	En katalog över hela Sveriges befolkning.
6 miljarder	32,5	33	En katalog över hela jordens befolkning.

Ett sätt att illustrera sökningen är som ett binärt sökträd där varje nod i trädet har maximalt två barn det ena måste vara större än och det andra mindre än nodens egna element. Alla noder i trädet är element i listan. Trädets höjd är högsta antalet uppslagningar som sökningen kräver.

Algoritm

Binärsökning söker igenom sorterade listor. Binärsökning börjar med att jämföra elementet i mitten av listan med det sökta värdet. Om det sökta värdet är lika med elementet i mitten av listan, returneras dess position i listan. Om det sökta värdet är mindre eller större än elementet i mitten av listan, så fortsätter sökningen i den lägre respektive högre halvan av listan, rekursivt.

Procedur

Följande samling av instruktioner utgör en binärsökningsalgoritm för att hitta positionen av värdet T i listan A, som innehåller n element med värdena A₀ , A_{1, ...,} A_n-1.

1. Sätt L till 0 och R till n − 1.
2. Om L > R, så har binärsökningen misslyckats.
3. Sätt m (positionen av elementet i mitten av listan) till heltalsdelen av (L + R) / 2.
4. Om A_m < T, sätt L till m + 1 och gå till steg 2.
5. Om A_m > T, sätt R till m − 1 och gå till steg 2.
6. Nu är A_m = T, sökningen är färdig; returnera m.

Den iterativa proceduren håller reda på sökområdet med de två variablerna (L och R).