Kuidas töötab binaarotsing järjestatud nimekirjas?

Kakupuu otsing on algoritm, mis kasutatakse elementide leidmiseks sorteeritud nimekirjas, mille keerukus on logaritmiline O(log n). See töötab põhimõttel "jaga ja valitse":

1. Määratakse nimekirja keskne element.
2. Kui otsitav element on võrdne keskmega, otsing lõpeb.
3. Kui otsitav element on väiksem kui keskne, jätkatakse otsingut vasakul poolel nimekirjast.
4. Kui suurem, siis paremal poolel.

Protsess kordub rekursiivselt või iteratiivselt, kuni element leitakse või otsingu vahemik ammendub.

Näide Go keeles:

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1 // elementi ei leitud
}