Comment fonctionne la recherche binaire dans une liste triée?

La recherche binaire est un algorithme pour rechercher un élément dans une liste triée avec une complexité logarithmique O(log n). Il fonctionne selon le principe de "diviser pour régner":

1. On détermine l'élément médian de la liste.
2. Si l'élément recherché est égal au médian, la recherche se termine.
3. Si l'élément recherché est inférieur au médian, la recherche continue dans la moitié gauche de la liste.
4. Si supérieur, dans la moitié droite.

Le processus se répète de manière récursive ou itérative jusqu'à ce que l'élément soit trouvé ou que la plage de recherche soit épuisé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é
}