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.

Binärsökning
Sökalgoritm, söndra-och-härska-algoritm Redigera Wikidata
Binärsökningsträd med 9 noder och höjden 4.

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 uppslagningar eller halveringar för att hitta rätt ställe, eller 2-logaritmen avrundad uppåt.

Antal noder
2-logaritmen
avrundad uppåt
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

redigera

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

redigera

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 A0 , A1, ..., An-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 Am < T, sätt L till m 1 och gå till steg 2.
  5. Om Am > T, sätt R till m − 1 och gå till steg 2.
  6. Nu är Am = 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).