Чӣ тавр мураккабии вақти алгоритми ҷустуҷӯи дугона муайян карда мешавад؟

Мӯҳлати вақтии алгоритми ҷустуҷӯи дугона ҳамчун O(log n) муайян карда мешавад, ки дар он n шумораи унсурҳои дар массиви тартибдодашуда мебошад. Ин ба он вобаста аст, ки дар ҳар қадам алгоритм минтақаи ҷустуҷӯро ба ду тақсим мекунад, ки боиси кам шудани шумораи унсурҳои баррасишаванда ба нисфи он мегардад, то он ки унсури ҷустуҷӯӣ ё набудани он тасдиқ карда шавад.

Масалан дар Go:

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 // унсур ёфт нашуд
}