Cum se determină complexitatea temporală a algoritmului de căutare binară?

Complexitatea temporală a algoritmului de căutare binară este definită ca O(log n), unde n reprezintă numărul de elemente din array-ul sortat. Acest lucru se datorează faptului că, la fiecare pas, algoritmul împarte zona de căutare în două, reducând numărul de elemente considerate la jumătate, până când găsește elementul căutat sau confirmă absența sa.

Exemplu î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 // elementul nu a fost găsit
}