Какова сложность бинарного поиска и почему?

Сложность бинарного поиска — O(log n), где 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 // элемент не найден
}