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