binærsøk

Algoritmen er svært enkel. Man går til midten av en liste og ser om elementet der er større eller mindre enn det elementet man leter etter. Hvis det er større, så vet man at elementet ligger til venstre for midten, ellers ligger elementet til høyre for midten. Man gjentar prosessen i riktig halvdel helt til man kun har ett element igjen. Da har man enten funnet riktig element eller funnet ut at elementet man søker ikke eksisterer.

Eksempel: Man har en sortert liste [1, 2, 4, 6, 7, 9, 11, 17, 21]. Hvis man leter etter tallet 11 i den foregående listen, så vil man se på det midterste tallet, som i dette eksempelet er 7, og finne ut at dersom 11 er i listen, så må det ligge i høyre halvdel av listen.

Hvis en sortert liste har N elementer, så vil algoritmen bruke log N mange sammenligninger. I tilfellene hvor listen av elementer ikke er sortert på forhånd, må man sjekke hvert enkelt element, og derfor bruke N mange sammenligninger. En algoritme som bruker log N tid er svært rask, og kan derfor kjøres på veldig store datamengder. For eksempel er log av 1 million kun 20, og log av 1 milliard er 30. Det vil si at dersom man trenger å søke frem et element i en sortert liste med 1 milliard elementer, så trenger man bare 30 sammenligninger, noe en datamaskin typisk kan gjøre på under et millisekund.

La oss si at man har 80 lukkede skap på rekke, og inni hvert skap står et navn og et telefonnummer. Oppgaven er å finne telefonnummeret til Kari Nordmann, men man vet ikke hva som er hennes skap. Hvis skapene er i vilkårlig rekkefølge, så har man ikke noe annet alternativ enn å sjekke hvert skap. Hvis man derimot vet at skapene er sortert på etternavn, så sjekker man først skap nummer 40. Hvis navnet i skap 40 er Olsen, så vet man at Kari Nordmann må ha skap mellom 0 og 40. Da sjekker man skap 20. I snitt må man sjekke 7 skap.

• algoritme
• sorteringsalgoritme
• stordata
• kompleksitetsklasser