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.
Algoritm
redigeraBinä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
redigeraFö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.
- Sätt L till 0 och R till n − 1.
- Om L > R, så har binärsökningen misslyckats.
- Sätt m (positionen av elementet i mitten av listan) till heltalsdelen av (L + R) / 2.
- Om Am < T, sätt L till m + 1 och gå till steg 2.
- Om Am > T, sätt R till m − 1 och gå till steg 2.
- 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).