Care este complexitatea căutării binare și de ce?

Complexitatea căutării binare este O(log n), unde n reprezintă numărul de elemente din array-ul sortat. Acest lucru se datorează faptului că, la fiecare pas, algoritmul împarte zona de căutare în două, eliminând jumătate din elemente care nu pot conține valoarea căutată. Astfel, numărul de operații crește logaritmic în raport cu dimensiunea datelor de intrare.

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
}