Search Insert Position

Условие

Дан отсортированный по возрастанию массив уникальных целых чисел nums и целевое число target. Необходимо вернуть индекс, по которому следует вставить target, чтобы сохранить порядок сортировки массива. Если target уже присутствует в массиве, вернуть его текущий индекс.

Примеры

Input: nums = [1, 3, 5, 6], target = 5

Output: 2

Explanation: Число 5 уже есть в массиве на индексе 2.

Input: nums = [1, 3, 5, 6], target = 2

Output: 1

Explanation: Число 2 должно быть вставлено на индекс 1, чтобы сохранить порядок.

Input: nums = [1, 3, 5, 6], target = 7

Output: 4

Explanation: Число 7 должно быть вставлено на индекс 4.

Решение

fun searchInsert(nums: IntArray, target: Int): Int {
    // Инициализация указателей для границ поиска
    var left = 0
    var right = nums.size - 1

    // Выполняем бинарный поиск
    while (left <= right) {
        // Вычисляем индекс середины
        val mid = left + (right - left) / 2

        // Если значение в середине равно target, возвращаем mid
        if (nums[mid] == target) {
            return mid
        } else if (nums[mid] > target) { // Если target меньше значения в середине, сдвигаем правую границу
            right = mid - 1
        } else { // Если target больше, сдвигаем левую границу
            left = mid + 1
        }
    }
    // Возвращаем индекс, по которому нужно вставить target
    return left
}

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

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

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

O(1) — дополнительной памяти не требуется, так как операция выполняется на месте.