Quelle est la complexité de la recherche binaire et pourquoi?

La complexité de la recherche binaire est de 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, en écartant la moitié des éléments qui ne peuvent pas contenir la valeur recherchée. Ainsi, le nombre d'opérations croît logarithmiquement en fonction de la taille des données d'entrée.

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é
}