![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/langsv-640px-Binary_search_tree.svg.png&w=640&q=50)
Binärsökning
From Wikipedia, the free encyclopedia
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/250px-Binary_search_tree.svg.png)
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.