Qual è la complessità della ricerca binaria e perché?

La complessità della ricerca binaria è O(log n), dove n è il numero di elementi nell'array ordinato. Ciò è dovuto al fatto che ad ogni passo l'algoritmo divide l'area di ricerca a metà, scartando la metà degli elementi che non possono contenere il valore cercato. In questo modo, il numero di operazioni cresce logaritmicamente rispetto alla dimensione dei dati di input.

Esempio in 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 // elemento non trovato
}