Binærsøk

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

Kategori:Algoritmer