Kaip nustatoma dvejetainio paieškos algoritmo laiko sudėtingumas?

Dvigubo paieškos algoritmo laiko sudėtingumas apibrėžiamas kaip O(log n), kur n yra surūšiuoto masyvo elementų skaičius. Tai yra todėl, kad kiekviename žingsnyje algoritmas dalija paieškos sritį perpus, sumažindamas nagrinėjamų elementų skaičių perpus, kol suranda ieškomą elementą arba patvirtina jo nebuvimą.

Pavyzdys Go kalba:

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 // elementas nerastas
}