Cum funcționează căutarea binară într-o listă sortată?

Căutarea binară este un algoritm pentru găsirea unui element într-o listă sortată cu o complexitate logaritmică O(log n). Funcționează după principiul "împarte și cucerește":

1. Se determină elementul mediu al listei.
2. Dacă elementul căutat este egal cu cel mediu, căutarea se încheie.
3. Dacă elementul căutat este mai mic decât cel mediu, căutarea continuă în jumătatea stângă a listei.
4. Dacă este mai mare, în jumătatea dreaptă.

Procesul se repetă recursiv sau iterativ până când elementul este găsit sau intervalul de căutare se epuizează.

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
}