Comment la complexité temporelle de l'algorithme de recherche binaire est-elle déterminée?

La complexité temporelle de l'algorithme de recherche binaire est définie comme O(log n), où n est le nombre d'éléments dans le tableau trié. Cela est dû au fait qu'à chaque étape, l'algorithme divise la zone de recherche en deux, réduisant le nombre d'éléments considérés de moitié, jusqu'à ce qu'il trouve l'élément recherché ou qu'il en soit convaincu de son absence.

Exemple en 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 // élément non trouvé
}