Binärsökning
Från Rilpedia
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 innhå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 N |
2-logaritmen log2N |
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 | |
| 277 197 | 18 | 19 | Alla artiklar i svenska 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.
