Дано: отсортированный массив целых чисел и целочисленное значение target, верните индекс target. Если target нету в списке , верните индекс, в котором он находилась бы.
Примечание: алгоритм должен иметь сложностью O(log n).
Пример :
Вход: nums = [1,3,5,6], target = 5
Выход: 2
Ограничения:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums содержит целые значения, отсортированные по возрастанию.
-104 <= target <= 104
Без ограничения O(log n) можно решить задачу простым перебором списка.
def searchInsert(nums: List[int], target: int) -> int:
if not nums:
return 0
for i, num in enumerate(nums):
if num >= target:
return i
return len(nums)
Но тут сложность O(n) так, что не подходит.
Решение(Python):
1) Бинарный поиск:
def searchInsert(nums: List[int], target: int) -> int:
min = 0
max = len(nums)
while min < max:
m = (min + max) // 2
if nums[m] == target:
return m
if nums[m] < target:
min = m + 1
else:
max = m
return min
Применяется обычный алгоритм бинарного(двоичного) поиска
- Находится средний элемент последовательности. Для этого первый и последний индексы связываются с переменными, а индекс среднего элемента вычисляется.
- Значение среднего элемента сравнивается с искомым значением. Если значение среднего элемента оказывается равным искомому, поиск завершается.
- Иначе, в зависимости от того, искомое значение больше или меньше значения среднего элемента, дальнейший поиск будет происходить только в левой или только в правой половинах массива.
- Для этого одна из границ исследуемой последовательности сдвигается. Если искомое значение больше значения среднего элемента, то нижняя граница сдвигается за средний элемент на один элемент справа. Если искомое значение меньше значения среднего элемента, то верхняя граница сдвигается на элемент перед средним.
- Снова находится средний элемент теперь уже в выбранной половине. Описанный выше алгоритм повторяется для данного среза.
Временная сложность: O(logN) (так как мы уменьшаем срез массива на 2 на каждой итерации и проверяем только 1 элемент),
Пространственная сложность: O(1).
2) Использования модуля bisect
Модуль bisect - обеспечивает поддержку списка в отсортированном порядке с помощью алгоритма бинарного поиска.
import bisect
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect.bisect_left(nums, target)
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)¶
Находит индекс вставки для x в a для отсортированного массива
Временная сложность: O(logN) (так как мы уменьшаем срез массива на 2 на каждой итерации и проверяем только 1 элемент),
Пространственная сложность: O(1).
