Hur fungerar Binärsökning?
Binärsökning fungerar genom att upprepade gånger dela listan i hälften. Den börjar med att jämföra det sökta värdet med mittenvärdet i listan. Om mittenvärdet är lika med det sökta värdet har vi hittat det. Om det sökta värdet är mindre än mittenvärdet fortsätter vi sökningen i den vänstra halvan, annars i den högra halvan. Denna process upprepas tills vi hittar värdet eller tills det inte finns fler element att söka igenom. I exemplet till höger demonstreras hur algoritmen fungerar för att söka efter siffran 7 i en lista bestående av 15 tal.Testa klicka nästa för att se den verka steg-för-steg!
Algoritmen steg för steg:
- Börja med en sorterad lista
- Jämför det sökta värdet med mittenvärdet
- Om mittenvärdet är lika med det sökta värdet, har vi hittat det
- Om det sökta värdet är mindre än mittenvärdet, sök i den vänstra halvan
- Om det sökta värdet är större än mittenvärdet, sök i den högra halvan
- Gå tillbaka till steg 2
Varför kallas det "Binärsökning"?
Namnet kommer från hur algoritmen delar listan i hälften (binärt) för varje steg. Detta gör den mycket effektivare än till exempel linjära sökmetoder.
När används det?
Binärsökning används när man har en sorterad lista och vill hitta ett värde snabbt. Det är mycket snabbare än att gå igenom varje element ett i taget.