Kako se određuje vremenska složenost algoritma binarnog pretraživanja?

Vremenska složenost binarnog pretraživačkog algoritma definisana je kao O(log n), gde n predstavlja broj elemenata u sortiranom nizu. To je zato što na svakom koraku algoritam deli opseg pretraživanja na pola, smanjujući broj razmatranih elemenata na polovinu, dok ne pronađe traženi element ili potvrdi njegovu odsutnost.

Primer u 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 // element nije pronađen
}