Условие

Дан массив целых чисел nums, отсортированный по возрастанию, и целое число target.

Вернуть индекс target, если он существует в nums. Иначе вернуть -1.

Вы должны написать алгоритм со сложностью O(log n).

Примеры

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9 Output: 4 Explanation: 9 находится в nums[4].

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2 Output: -1 Explanation: 2 нет в массиве.

Решение

fun search(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    // Повторяем, пока есть элементы для проверки
    while (left <= right) {
        // Находим средний индекс, чтобы избежать переполнения
        val mid = left + (right - left) / 2
        // Если средний элемент равен цели, возвращаем его индекс
        if (nums[mid] == target) return mid
        // Если средний элемент меньше цели, сдвигаем левую границу
        if (nums[mid] < target) {
            left = mid + 1
        } else {
            // Если средний элемент больше цели, сдвигаем правую границу
            right = mid - 1
        }
    }
    // Если элемент не найден, возвращаем -1
    return -1
}

Временная сложность

O(log n), так как каждый шаг уменьшает размер массива вдвое.

Пространственная сложность

O(1), так как используется только несколько дополнительных переменных.