Binärsökning

Från Wikipedia
Hoppa till: navigering, 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 \lceil\log_2 N\rceil uppslagsningar 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 950 678 20.8 21 Alla artiklar i svenskspråkiga Wikipedia.
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.