Какая средняя алгоритмическая сложность поиска значения в сортированном массиве

Бинарный поиск в отсортированном массиве имеет сложность O(log n), где n — количество элементов. Это связано с тем, что на каждом шаге алгоритм делит массив пополам, отбрасывая половину элементов.

Пример на Kotlin:

fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1
}