Двоичный поиск по ответу

живой пример

import java.util.ArrayList;
import java.util.List;

public class MinSpeed {
    public static void main(String[] args) {
        int[] piles = {30, 11, 23, 4, 20};
        int h = 6;
        int top = 0;
        for (int p : piles) top = Math.max(top, p);
        int low = 1;
        int high = top;
        List<String> steps = new ArrayList<>();
        while (low < high) {
            int mid = low + (high - low) / 2;
            long hours = 0;
            for (int p : piles) hours += (p + mid - 1) / mid;
            steps.add(mid + (hours <= h ? " да" : " нет"));
            if (hours <= h) high = mid;
            else low = mid + 1;
        }
        System.out.println("проверяли скорости: " + String.join(", ", steps));
        System.out.println("ответ: " + low + " (проверок " + steps.size() + " из " + top + ")");
    }
}

живой пример

package main

import (
	"fmt"
	"strings"
)

func main() {
	piles := []int{30, 11, 23, 4, 20}
	h := 6
	top := 0
	for _, p := range piles {
		top = max(top, p)
	}
	low, high := 1, top
	var steps []string
	for low < high {
		mid := low + (high-low)/2
		hours := 0
		for _, p := range piles {
			hours += (p + mid - 1) / mid
		}
		if hours <= h {
			steps = append(steps, fmt.Sprintf("%d да", mid))
			high = mid
		} else {
			steps = append(steps, fmt.Sprintf("%d нет", mid))
			low = mid + 1
		}
	}
	fmt.Println("проверяли скорости:", strings.Join(steps, ", "))
	fmt.Printf("ответ: %d (проверок %d из %d)\n", low, len(steps), top)
}

живой пример

const piles = [30, 11, 23, 4, 20];
const h = 6;
const top = Math.max(...piles);
let low = 1;
let high = top;
const steps = [];
while (low < high) {
  const mid = low + Math.floor((high - low) / 2);
  let hours = 0;
  for (const p of piles) hours += Math.ceil(p / mid);
  steps.push(`${mid} ${hours <= h ? "да" : "нет"}`);
  if (hours <= h) high = mid;
  else low = mid + 1;
}
console.log("проверяли скорости:", steps.join(", "));
console.log(`ответ: ${low} (проверок ${steps.length} из ${top})`);

живой пример

piles = [30, 11, 23, 4, 20]
h = 6
top = max(piles)
low, high = 1, top
steps = []
while low < high:
    mid = low + (high - low) // 2
    hours = sum((p + mid - 1) // mid for p in piles)
    steps.append(f"{mid} {'да' if hours <= h else 'нет'}")
    if hours <= h:
        high = mid
    else:
        low = mid + 1
print("проверяли скорости:", ", ".join(steps))
print(f"ответ: {low} (проверок {len(steps)} из {top})")

Сам поиск по ответу в стандартной библиотеке не найти, и это ожидаемо: «массива» в такой задаче нет, а есть проверка, которую вы пишете под условие, — цикл с делением диапазона тут всегда свой. А вот поиск границы среди уже сохранённых данных реализован давно, и переписывать его руками смысла нет.

Для отсортированного массива это Arrays.binarySearch, для списка — Collections.binarySearch: внутри тот же цикл с делением диапазона пополам, только середину там считают беззнаковым сдвигом ((low + high) >>> 1) — приём против переполнения из той же семьи, что и low + (high - low) / 2 выше.

И отвечают они не только «есть или нет»: когда точного совпадения нет, возвращается -(позиция вставки) - 1, то есть та самая граница «первый подходящий», ради которой обычно и пишут свой поиск; подробности и главная их грабля разобраны в статье о массивах.

Ту же задачу «первый подходящий» решают и TreeSet с TreeMap, только не в массиве, а в дереве. Внутри у них красно-чёрное дерево: двоичное дерево поиска, которое при вставках подкручивает свою форму само, поэтому глубина остаётся порядка log N и не вырождается в список даже на данных, приходящих по возрастанию. Отсюда сложность: add, contains, get, remove — O(log N), а firstKey и lastKey — O(log N) на спуск к краю. И там же живут методы, которые отвечают ровно на вопрос «первый подходящий»: ceiling(x) отдаёт наименьший элемент не меньше x, floor(x) — наибольший не больше, higher и lower — то же самое строго, а headMap, tailMap и subMap возвращают целый диапазон ключей. Та же граница между «не подходит» и «подходит», только ищется она среди хранимых ключей, а не вычисляется проверкой:

живой пример

import java.util.List;
import java.util.TreeSet;

public class Boundary {
    public static void main(String[] args) {
        TreeSet<Integer> speeds = new TreeSet<>(List.of(4, 7, 11, 18, 25));
        System.out.println("первая не меньше 12: " + speeds.ceiling(12));
        System.out.println("последняя не больше 12: " + speeds.floor(12));
        System.out.println("весь хвост от 12: " + speeds.tailSet(12));
    }
}

Грабля у деревьев своя, и она тихая: порядок для них — это и есть определение равенства. TreeSet считает два элемента одинаковыми, когда сравнение вернуло ноль, и на equals при этом не смотрит вовсе. Если компаратор написан, скажем, только по цене, то второй товар с той же ценой в множество просто не попадёт — без исключения, без предупреждения, add вернёт false, а вы этого не проверяли. Сравнение в дереве должно различать ровно то же, что различает equals; иначе структура молча теряет данные.

Сам поиск по ответу в стандартной библиотеке Go есть, и это редкость среди языков: sort.Search(n, f) возвращает наименьший индекс i из [0, n), для которого f(i) истинно, и требует от f ровно той монотонности, о которой шла речь выше. Проверку вы пишете сами, а цикл с делением диапазона, инвариантом и защитой от переполнения написан за вас.

Для отсортированного среза это slices.BinarySearch, а для своего порядка slices.BinarySearchFunc: внутри тот же цикл с делением диапазона пополам, только середину там считают беззнаковым сдвигом, приём против переполнения из той же семьи, что и low + (high - low) / 2 выше. Отвечают они не только «есть или нет»: вторым значением идёт found, а первым — позиция, куда элемент надо вставить, то есть та самая граница «первый подходящий», ради которой обычно и пишут свой поиск; подробности разобраны в статье о массивах.

Упорядоченного множества с ceiling и floor, как TreeSet в Java, в стандартной библиотеке нет; ту же задачу на хранимых данных решает отсортированный срез: ceiling(x) это элемент по индексу из BinarySearch, floor(x) — элемент перед ним, а «весь хвост от x» — срез от этого индекса. Пока вставок мало, это быстрее любого дерева; когда данные постоянно меняются, берут пакет github.com/google/btree с AscendGreaterOrEqual, разобрано в статье про двоичные деревья. Та же граница между «не подходит» и «подходит», только ищется среди хранимых значений:

живой пример

package main

import (
	"fmt"
	"slices"
	"sort"
)

func main() {
	piles := []int{30, 11, 23, 4, 20}
	h, top := 6, 30
	speed := 1 + sort.Search(top, func(i int) bool {
		hours := 0
		for _, p := range piles {
			hours += (p + i) / (i + 1)
		}
		return hours <= h
	})
	fmt.Println("минимальная скорость через sort.Search:", speed)

	speeds := []int{4, 7, 11, 18, 25}
	i, _ := slices.BinarySearch(speeds, 12)
	fmt.Println("первая не меньше 12:", speeds[i])
	fmt.Println("последняя не больше 12:", speeds[i-1])
	fmt.Println("весь хвост от 12:", speeds[i:])
}

sort.Search ищет по индексам от нуля, поэтому скорость mid превращается в индекс mid - 1, отсюда (p + i) / (i + 1) и единица в ответе. Ответ тот же, что у цикла выше: 23.

Грабля у sort.Search своя, и она тихая: если f не монотонна, функция не упадёт и ничего не заметит, а вернёт какой-то индекс, на котором f случайно оказалась истинной. И вторая, из той же статьи о массивах: на неотсортированном срезе BinarySearch тоже молчит и возвращает мусор. Обе лечатся одинаково — монотонность проверки и порядок среза это ваша обязанность, библиотека их не проверяет.

Сам поиск по ответу в стандартной библиотеке не найти, и это ожидаемо: «массива» в такой задаче нет, а есть проверка, которую вы пишете под условие, — цикл с делением диапазона тут всегда свой. Но и поиска границы среди уже сохранённых данных в JavaScript тоже нет: ни двоичного поиска по массиву, ни упорядоченного множества с ceiling и floor. Функцию lowerBound пишут один раз и кладут в утилиты проекта.

Она и есть граница «первый подходящий»: возвращает индекс первого элемента, который не меньше искомого, или длину массива, если такого нет. Внутри тот же цикл с делением диапазона пополам; середину считают как (lo + hi) >>> 1, приём против переполнения из той же семьи, что и low + (high - low) / 2 выше, хотя в JavaScript до 2⁵³ переполнения нет. Через неё выражаются и ceiling(x) — элемент по найденному индексу, и floor(x) — элемент перед ним, и «весь хвост от x» — slice от индекса. Для данных, которые постоянно меняются, берут пакет вроде sorted-btree, разобрано в статье про двоичные деревья. Та же граница между «не подходит» и «подходит», только ищется среди хранимых значений:

живой пример

function lowerBound(a, key) {
  let lo = 0;
  let hi = a.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (a[mid] < key) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

const speeds = [4, 7, 11, 18, 25];
const i = lowerBound(speeds, 12);
console.log("первая не меньше 12:", speeds[i]);
console.log("последняя не больше 12:", speeds[i - 1]);
console.log("весь хвост от 12:", speeds.slice(i));

Та же функция с проверкой вместо сравнения превращается в поиск по ответу: lowerBound над диапазоном скоростей, где «меньше» значит «не успевает», и это ровно цикл из решения выше.

Грабля тут одна, и она тихая: indexOf и includes выглядят как поиск, но идут перебором и про порядок массива не знают; на отсортированном массиве в миллион элементов они в тысячи раз медленнее lowerBound, а результат тот же, поэтому подмену никто не замечает, пока не вырастут данные. И вторая, общая для всех языков: на неотсортированном массиве lowerBound не упадёт, а вернёт мусор — порядок это ваша обязанность.

Сам поиск по ответу в стандартной библиотеке есть, хоть и под другим именем: bisect_left с версии 3.10 принимает key=, и если скормить ему range возможных ответов с ключом-проверкой, он найдёт первый ответ, на котором проверка стала истинной. False меньше True, а проверка монотонна, значит, диапазон «ложь, ложь, …, истина, истина» отсортирован, и двоичный поиск по нему законен. Цикл с делением диапазона и инвариантом при этом написан за вас.

Для отсортированного списка это bisect_left и bisect_right: внутри тот же цикл с делением диапазона пополам, а переполнения индексов в Python не бывает, целые растут сколько нужно. Отвечают они не «есть или нет», а позицией, куда элемент надо вставить, то есть той самой границей «первый подходящий», ради которой обычно и пишут свой поиск; подробности разобраны в статье о массивах.

Упорядоченного множества с ceiling и floor, как TreeSet в Java, в стандартной библиотеке нет; ту же задачу на хранимых данных решает отсортированный список: ceiling(x) это элемент по индексу из bisect_left, floor(x) — элемент по индексу bisect_right(x) - 1, а «весь хвост от x» — срез от индекса. Когда данные постоянно меняются, берут SortedList из sortedcontainers, у которого те же bisect_left и irange работают за O(log N) вместе со вставкой; разобрано в статье про двоичные деревья. Та же граница между «не подходит» и «подходит», только ищется среди хранимых значений:

живой пример

from bisect import bisect_left, bisect_right

piles = [30, 11, 23, 4, 20]
h, top = 6, 30


def fits(speed: int) -> bool:
    return sum((p + speed - 1) // speed for p in piles) <= h


speed = bisect_left(range(1, top + 1), True, key=fits) + 1
print("минимальная скорость через bisect:", speed)

speeds = [4, 7, 11, 18, 25]
i = bisect_left(speeds, 12)
print("первая не меньше 12:", speeds[i])
print("последняя не больше 12:", speeds[bisect_right(speeds, 12) - 1])
print("весь хвост от 12:", speeds[i:])

range начинается с единицы, а bisect_left возвращает индекс внутри него, отсюда + 1. Ответ тот же, что у цикла выше: 23.

Грабля тут одна, и она тихая: bisect не проверяет ни порядок списка, ни монотонность ключа. На неотсортированных данных или с немонотонной проверкой он не упадёт, а вернёт какую-то позицию, на которой сравнение случайно сошлось. Порядок и монотонность это ваша обязанность, библиотека их не проверяет. И мелочь: x in sorted_list идёт перебором и про порядок не знает; на миллионе элементов bisect с проверкой a[i] == x быстрее в тысячи раз.

• Готовую границу среди сохранённых ключей отдают Arrays.binarySearch и ceiling/floor у TreeSet и TreeMap; сравнение в дереве и есть его равенство.

• Поиск по ответу готов: sort.Search(n, f) отдаёт первый индекс, где f истинна; границу среди хранимых значений даёт slices.BinarySearch на отсортированном срезе; монотонность и порядок не проверяются.

• Ни поиска по ответу, ни двоичного поиска в языке нет: одна функция lowerBound закрывает и границу в массиве, и поиск по ответу; indexOf идёт перебором.

• bisect_left с key= по range ответов и есть поиск по ответу; границу среди хранимых значений дают bisect_left и bisect_right; порядок и монотонность не проверяются.