Kokia yra dvejetainio paieškos sudėtingumas ir kodėl?

Dvigubo paieškos sudėtingumas yra 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, atmetant pusę elementų, kurie negali būti ieškomos vertės turėtojai. Taip operacijų skaičius auga logaritmiškai priklausomai nuo įvesties duomenų dydžio.

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
}