Базовый бинарный поиск, позиция вставки, поиск границ.
Бинарный поиск — не только для отсортированных массивов. Мощная техника для поиска ответа в пространстве решений с логарифмической сложностью O(log n)
Binary Search — алгоритм поиска, делящий диапазон поиска пополам на каждом шаге. Применяется не только к массивам, но и к пространству возможных ответов.
Монотонная функция — функция, которая только возрастает или только убывает.
Бинарный поиск — поиск делением диапазона пополам за O(log n).
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # Защита от переполнения
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # Не найденоdef binary_search_left(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] >= target:
result = mid
right = mid - 1 # Продолжаем поиск слева
else:
left = mid + 1
return resultdef binary_search_right(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] <= target:
result = mid
left = mid + 1 # Продолжаем поиск справа
else:
right = mid - 1
return resultУсловие:
Дан отсортированный по возрастанию массив целых чисел nums и целевое значение target. Напишите функцию для поиска target в nums.
Если target существует в массиве, верните его индекс. В противном случае верните -1.
Примеры:
Ввод: nums = [-1, 0, 3, 5, 9, 12], target = 9
Вывод: 4
Ввод: nums = [-1, 0, 3, 5, 9, 12], target = 2
Вывод: -1
Ограничения:
Решение:
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Объяснение:
mid = left + (right - left) // 2 защищает от переполненияleft <= right позволяет найти элемент в окне размера 1Сложность:
Условие:
Дан отсортированный по возрастанию массив целых чисел nums и целевое значение target. Найдите target в массиве и верните его индекс.
Если target не найден, верните индекс, куда он должен быть вставлен для сохранения порядка сортировки.
Примеры:
Ввод: nums = [1, 3, 5, 6], target = 5
Вывод: 2
Ввод: nums = [1, 3, 5, 6], target = 2
Вывод: 1
Ввод: nums = [1, 3, 5, 6], target = 7
Вывод: 4
Ограничения:
Решение:
def searchInsert(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left # Позиция вставкиОбъяснение:
left указывает на позицию вставкиleft — первый элемент > target (или len(nums))Сложность:
Условие:
Дан отсортированный по возрастанию массив целых чисел nums и целевое значение target.
Найдите начальную и конечную позицию target в массиве.
Примеры:
Ввод: nums = [5, 7, 7, 8, 8, 10], target = 8
Вывод: [3, 4]
Ввод: nums = [5, 7, 7, 8, 8, 10], target = 6
Вывод: [-1, -1]
Решение:
def searchRange(nums, target):
def find_left():
left, right = 0, len(nums) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] >= target:
result = mid
right = mid - 1
else:
left = mid + 1
return result
def find_right():
left, right = 0, len(nums) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] <= target:
result = mid
left = mid + 1
else:
right = mid - 1
return result
return [find_left(), find_right()]Объяснение:
find_left: ищем первый элемент ≥ targetfind_right: ищем последний элемент ≤ targetСложность:
Проблема: left < right vs left <= right.
# ❌ Неправильно для поиска элемента — может пропустить последний
while left < right:
...
# ✅ Правильно для поиска элемента
while left <= right: # Позволяет найти элемент в окне размера 1
...Почему это неправильно: При left < right цикл завершится, когда окно размера 1, и элемент может быть пропущен.
Проблема: (left + right) // 2 может переполниться.
# ❌ Неправильно — может переполниться
mid = (left + right) // 2
# ✅ Правильно — защита от переполнения
mid = left + (right - left) // 2| Задача | Ключевая идея |
|---|---|
| Binary Search | Классический поиск, left <= right |
| Search Insert | left указывает позицию вставки |
| Find First/Last | Два отдельных поиска |
Binary Search: Основы — базовый паттерн для поиска в отсортированных массивах.
Ключевые принципы:
left <= right для поиска элементаmid = left + (right - left) // 2 — защита от переполненияВопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.