Binärsökning

Från Wikipedia
Hoppa till navigering Hoppa till sök
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 uppslagsningar 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 | redigera wikitext]

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, returnera 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 | redigera wikitext]

Givet en lista A av n element med värden A0 , A1, ..., An-1, det sökta värdet T, så använder följande samling av instruktioner binärsökning för att hitta positionen av värdet T i A.

  1. Sätt L to 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).