Binærsøk
 | Kildeløs: Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet. Helt uten kilder.
(10. okt. 2015) |
Binærsøk er en effektiv algoritme for å finne fram til et bestemt element i en sortert liste ved å dele listen i to for hvert steg. Algoritmen tar det midterste elementet i den sorterte listen og sammenligner med det elementet en skal finne fram til for å finne ut om det er større eller mindre. Fordi listen er sortert vet en dermed om elementet kommer før eller etter, og søker deretter i den gjenstående halvdelen på samme måte.
Her er pseudokode for en funksjon som ser på den verdien i den sorterte listen a som ligger midt mellom plasseringene left og right. Funksjonen kaller seg selv rekursivt med den ene halvdelen av listen.
function binarySearch(a, value, left, right)
if right < left
return not found
mid := floor((left+right)/2)
if value > a[mid]
return binarySearch(a, value, mid+1, right)
else if value < a[mid]
return binarySearch(a, value, left, mid-1)
else
return mid