Используйте бинарный поиск первой позиции, где элемент не меньше target: это и индекс совпадения, и место вставки при его отсутствии. Время O(log n), память O(1).
Получив отсортированный массив различных целых чисел и целевое значение, верните индекс, если цель найдена. Если нет, верните индекс в том месте, где он был бы, если бы он был вставлен по порядку.
Используйте бинарный поиск первой позиции, где элемент не меньше target: это и индекс совпадения, и место вставки при его отсутствии. Время O(log n), память O(1).
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Получив отсортированный массив различных целых чисел и целевое значение, верните индекс, если цель найдена. Если нет, верните индекс в том месте, где он был бы, если бы он был вставлен по порядку.
Пример 1:
Input: nums = [1,3,5,6], target = 5 Output: 2
Пример 2:
Input: nums = [1,3,5,6], target = 2 Output: 1
Пример 3:
Input: nums = [1,3,5,6], target = 7 Output: 4
Ответ
Используйте бинарный поиск первой позиции, где элемент не меньше target: это и индекс совпадения, и место вставки при его отсутствии. Время O(log n), память O(1).
Поддерживаем полуинтервал [left, right):
def search_insert(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
Для [1, 3, 5, 6] результаты с target 5, 2 и 7 равны 2, 1 и 4. Пустой массив даёт 0. Вставку выполнять не нужно: задача требует только позицию. В стандартной библиотеке аналогичный поиск делает bisect_left.