Kuidas määratakse binaarse otsingu algoritmi ajaliseline keerukus?

Binaarse otsingu algoritmi ajakulud määratletakse kui O(log n), kus n on järjestatud massiivi elementide arv. See tuleneb sellest, et iga sammu jooksul jagab algoritm otsinguala kaheks, vähendades vaadeldavate elementide arvu poole võrra, kuni leitakse otsitav element või kinnitatakse selle puudumine.

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
}