Mis on binaarse otsingu keerukus ja miks?

Binaarse otsingu keerukus on O(log n), kus n on järjestatud massiivi elementide arv. See on tingitud sellest, et iga sammu jooksul jagab algoritm otsinguala pooleks, välistades poole elementidest, mis ei saa sisaldada otsitavat väärtust. Seega kasvab operatsioonide arv logaritmiliselt sisendandmete suurusega.

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 // element ei leitud
}