Binary Search on Answer — Koko Eating, Ship Packages, Split Array.
Binary Search on Answer — поиск минимального/максимального возможного значения в пространстве решений.
def binary_search_on_answer():
left, right = min_possible, max_possible
result = -1
while left <= right:
mid = left + (right - left) // 2
if can_achieve(mid): # Проверяем, возможно ли значение mid
result = mid
right = mid - 1 # Пробуем меньше (ищем минимум)
else:
left = mid + 1 # Нужно больше
return resultУсловие:
Коко любит бананы. Есть n кучек бананов, i-я кучка имеет piles[i] бананов. Охранники ушли и вернутся через h часов.
Коко может решить, с какой скоростью k (бананов в час) она будет есть. Каждый час она выбирает какую-то кучку и съедает k бананов из неё.
Верните минимальное целое k, такое что Коко сможет съесть все бананы за h часов.
Примеры:
Ввод: piles = [3, 6, 7, 11], h = 8
Вывод: 4
Ввод: piles = [30, 11, 23, 4, 20], h = 5
Вывод: 30
Решение:
import math
def minEatingSpeed(piles, h):
def can_eat_all(speed):
hours = sum(math.ceil(pile / speed) for pile in piles)
return hours <= h
left, right = 1, max(piles)
result = right
while left <= right:
mid = left + (right - left) // 2
if can_eat_all(mid):
result = mid
right = mid - 1 # Пробуем меньшую скорость
else:
left = mid + 1 # Нужно больше
return resultОбъяснение:
can_eat_all(speed) проверяет, можно ли съесть все за h часовСложность: O(n × log m), где n = len(piles), m = max(piles)
Условие:
Конвейерная лента содержит грузы. i-й груз имеет вес weights[i].
Каждый день мы загружаем корабль грузами с конвейера в том порядке, в котором они идут. Верните минимальную грузоподъёмность корабля, чтобы все грузы были доставлены за days дней.
Примеры:
Ввод: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Вывод: 15
Ввод: weights = [3, 2, 2, 4, 1, 4], days = 3
Вывод: 6
Решение:
def shipWithinDays(weights, d):
def can_ship(capacity):
days = 1
current_load = 0
for w in weights:
if current_load + w > capacity:
days += 1
current_load = w
else:
current_load += w
return days <= d
left = max(weights) # Минимум: самый тяжёлый груз
right = sum(weights) # Максимум: все за один день
result = right
while left <= right:
mid = left + (right - left) // 2
if can_ship(mid):
result = mid
right = mid - 1
else:
left = mid + 1
return resultОбъяснение:
can_ship(capacity) симулирует погрузкуСложность: O(n × log(sum(weights)))
Условие:
Дан массив неотрицательных целых чисел nums и целое число k.
Разделите массив на k непустых непрерывных подмассивов так, чтобы максимальная сумма среди этих подмассивов была минимальной.
Примеры:
Ввод: nums = [7, 2, 5, 10, 8], k = 2
Вывод: 18
Объяснение: [7, 2, 5] и [10, 8], максимальная сумма = 18
Решение:
def splitArray(nums, k):
def can_split(max_sum):
count = 1
current_sum = 0
for num in nums:
if current_sum + num > max_sum:
count += 1
current_sum = num
if count > k:
return False
return True
left = max(nums) # Минимум: максимальный элемент
right = sum(nums) # Максимум: вся сумма
result = right
while left <= right:
mid = left + (right - left) // 2
if can_split(mid):
result = mid
right = mid - 1
else:
left = mid + 1
return resultОбъяснение:
can_split(max_sum) проверяет, можно ли разделить на ≤ k подмассивовСложность: O(n × log(sum(nums)))
Условие:
Дана n x n матрица matrix, где каждая строка и столбец отсортированы по возрастанию.
Найдите k-й наименьший элемент в отсортированном порядке.
Примеры:
Ввод: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Вывод: 13
Решение:
def kthSmallest(matrix, k):
n = len(matrix)
left, right = matrix[0][0], matrix[n-1][n-1]
def count_less_equal(target):
count = 0
row, col = n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= target:
count += row + 1
col += 1
else:
row -= 1
return count
result = -1
while left <= right:
mid = left + (right - left) // 2
if count_less_equal(mid) >= k:
result = mid
right = mid - 1
else:
left = mid + 1
return resultОбъяснение:
count_less_equal(target) считает элементы ≤ target за O(n)Сложность: O(n × log(max - min))
| Задача | Диапазон поиска | Проверка |
|---|---|---|
| Koko Eating | [1, max(piles)] | can_eat_all(speed) |
| Ship Packages | [max(weights), sum(weights)] | can_ship(capacity) |
| Split Array | [max(nums), sum(nums)] | can_split(max_sum) |
| K-th Smallest | [min, max] матрицы | count_less_equal(target) |
# ❌ Неправильно для Ship Packages
left = 0 # Не может быть 0!
# ✅ Правильно
left = max(weights) # Минимум: самый тяжёлый груз# ❌ Неправильно — нет result
while left <= right:
if can_achieve(mid):
right = mid - 1 # Но не сохраняем mid!
# ✅ Правильно
result = -1
while left <= right:
if can_achieve(mid):
result = mid # Сохраняем возможный ответ
right = mid - 1Binary Search: Поиск ответа — поиск оптимального значения в пространстве решений.
Ключевые принципы:
Далее: Binary Search: Минимум/Максимум