Бинарный поиск и поиск по ответу

Перед началом: куча и приоритетные очереди (модуль 9), сортировки и их сложность (модуль 8). Инструменты: Go 1.27, sort.Search, slices.BinarySearch. Трудоёмкость: ~6 ч (теория 2.5 ч · практика 3.5 ч).

🔥 Инцидент: «Запись есть, а мониторинг показывает „нет данных"»

Мониторинг хранит точки метрики отсортированными по времени, а панель ищет последнюю точку «не позже момента T». Поиск инженер написал сам: hi := len(a)-1 (закрытая граница), цикл for lo < hi и внутри if a[mid] <= t { lo = mid } — пять строк, два дефекта. Проявились они по-разному: часть запросов висела до таймаута («нет данных» на панели), а на других точка в конце среза вообще не проверялась — for lo < hi при hi = len−1 оставляет последний индекс вне интервала, а когда он сужался до двух элементов, lo = mid не двигал границу, и цикл крутился вечно. Чаще всего пропадали свежие точки: они лежат в конце среза, а спрашивают их чаще всего.

В модуле лечим причину: явный инвариант поиска, одна конвенция границ без смешивания, доказательство прогресса на каждом шаге, bound-ы руками и из stdlib — и поиск по ответу, где бинарный поиск идёт не по данным, а по значениям ответа.

📖 Теория

10.1 Инвариант важнее границ

Бинарный поиск держится не на «делим пополам», а на инварианте: пока интервал не пуст, ответ (если он есть) лежит внутри. Выбросить половину можно, только доказав, что ответа там нет. Конвенций две:

закрытая [lo, hi]: цикл lo <= hi, сдвиги mid ± 1;
полуоткрытая [lo, hi): цикл lo < hi, сдвиги hi = mid, lo = mid+1.

go
// Инвариант: если x есть, он лежит в [lo, hi]; каждый шаг сужает интервал.
lo, hi := 0, len(a)-1
for lo <= hi {
	switch mid := lo + (hi-lo)/2; {
	case a[mid] == x:
		return mid
	case a[mid] < x:
		lo = mid + 1 // mid проверен: прогресс гарантирован
	default:
		hi = mid - 1
	}
}
return -1

Смешивать конвенции нельзя — отсюда оба дефекта инцидента. Правило прогресса: каждый шаг строго уменьшает интервал. При hi = lo + 1 значение mid равно lo, поэтому lo = mid оставляет границу на месте — вечный цикл; тест на это считает шаги и падает после 2·log₂n.

![Сужение интервала lo, hi): на каждом шаге ответ остаётся внутри

10.2 Шаблон «первый true»: bound-ы руками

Половина задач — не «найти равное», а «найти границу»: первый не меньше x (lower bound), первый больше x (upper bound), точка вставки, первый плохой коммит — это поиск первого истинного предиката:

go
// Полуоткрытый [lo, hi): ответ — первый индекс с pred == true, иначе len(a).
lo, hi := 0, len(a)
for lo < hi {
	mid := lo + (hi-lo)/2
	if pred(a[mid]) {
		hi = mid // mid подходит, но ответ может быть левее
	} else {
		lo = mid + 1 // mid точно не ответ
	}
}
return lo

Lower bound — предикат a[i] >= x, upper bound — a[i] > x; разность даёт вхождения x за O(log n). Так же устроен и sort.Search.

10.3 stdlib: sort.Search, SearchInts, slices.BinarySearch

go
lo := sort.SearchInts(a, x)                  // первый a[i] >= x (lower bound)
if lo < len(a) && a[lo] == x { /* нашли */ } // SearchInts не проверяет равенство
found, pos := slices.BinarySearch(a, x)      // pos — lower bound; found честный

sort.Search(n, pred) — шаблон §10.2 функцией: первый истинный индекс или n;
sort.SearchInts — lower bound; «нашли или нет» проверяете сравнением;
slices.BinarySearch — (found, index), где index — точка вставки при false; slices.BinarySearchFunc — вариант с произвольным сравнением.

10.4 Поиск по ответу: бинарный поиск по предикату

Если ответ — число из [lo, hi], а проверка «подходит ли v» монотонна (подошло при v — подойдёт и при большем), перебирать значения не нужно: минимум подходящего ищется за O(log(hi−lo)) проверок.

go
// Коко ест бананы: минимальная скорость v, при которой уложится в h часов.
lo, hi := 1, maxPile // заведомо достижимая верхняя граница
for lo < hi {
	mid := lo + (hi-lo)/2
	if canFinish(piles, mid, h) {
		hi = mid // подходит — ищем минимальное слева
	} else {
		lo = mid + 1 // не подходит — нужно больше
	}
}
return lo

Тот же каркас: «груз корабля за D дней», «разрезать массив на m частей» (минимальная максимальная сумма), «мощность сервера под SLA». Проверка canFinish линейна, итого O(n log(диапазон)). Условие применимости — монотонность: если скидка растёт с объёмом, «уложиться в бюджет» ею уже не является, и поиск вернёт чушь без единой ошибки в коде.

10.5 Повёрнутый массив и локальные экстремумы

В повёрнутом массиве ([4,5,6,7,1,2,3]) одна из половин относительно mid всегда отсортирована — по ней и решаем: цель попадает в этот диапазон — идём туда, иначе — в другую половину.

go
// Повёрнутый массив: определяем, какая половина отсортирована.
if a[lo] <= a[mid] { // левая половина по порядку
	if a[lo] <= target && target < a[mid] {
		hi = mid - 1 // цель внутри левой
	} else {
		lo = mid + 1
	}
} else { /* зеркально: отсортирована правая половина */ }

Поиск пика проще: если a[mid] < a[mid+1] — подъём справа, значит пик там; иначе слева или сам mid. Сортировка не нужна: хватает локальной монотонности — хороший тест на понимание разницы.

10.6 Компромиссы

Решение	За	Против
Сортировка + бинарный поиск	O(n log n) один раз, O(log n) на запрос	Вставка O(n); сортировать на каждый запрос нельзя
`map`	Поиск и вставка O(1) в среднем	Память на бакеты, нет порядка и границ
Линейный проход	Ноль подготовки; на малых n быстрее	Не масштабируется при росте n и запросов
Ручной бинарный поиск	Полный контроль границ, bound-ы	Off-by-one и вечные циклы — инцидент модуля
`sort.Search`, `slices.BinarySearch`	Проверено stdlib, короче	Индекс и его семантику нужно помнить
Поиск по ответу	log(range) проверок вместо перебора	Без монотонности — мусор без ошибки

Правило: статичные данные и много запросов — сортировка + бинарный поиск; частые вставки и «есть ли» — map; один запрос — линейный проход; поиск по ответу — только после доказательства монотонности.

💻 Практика

Bound-ы руками. Реализуйте lowerBound и upperBound через шаблон «первый true». Тесты: пустой, все меньше, все больше, дубликаты, отсутствие x; сверка с sort.SearchInts, вхождения — ub − lb.
Разбор инцидента. Даны две функции: одна с hi = len−1 и циклом lo < hi, вторая с lo = mid в ветке <. Напишите тест-детектор по счётчику шагов (лимит 2·log₂n), найдите ломающие входы, исправьте обе и докажите завершение инвариантом.
Коко. minEatingSpeed(piles, h) из §10.4. Тесты: [3,6,7,11], h = 8 → 4; h = len(piles) → max(piles); огромный h → 1; одна куча. Проверьте монотонность: canFinish(v) не убывает по v.
Корабль и разрез. shipWithinDays(weights, days) и вариант splitArray(nums, m). Тесты: days = 1 → сумма всех; days ≥ len → максимум элемента; обоснуйте границы lo, hi. Что общего у предикатов?
Повёрнутый массив. searchRotated(a, target) — индекс или −1, без дубликатов. Тесты: без поворота, поворот на 1, на len−1, цель отсутствует, один элемент. Бонус: findPeak за O(log n).

🧩 Quiz

1. Что вернёт sort.SearchInts(a, x), если x в a отсутствует?

2. Что должен гарантировать инвариант бинарного поиска?

3. Почему lo = mid при hi = lo + 1 зацикливает поиск?

4. Как в повёрнутом массиве понять, где искать цель?

5. Что обязательно должно быть у задачи для поиска по ответу?

✅ Итоги модуля

Бинарный поиск — инвариант плюс гарантированный прогресс: одна конвенция границ, никаких lo = mid, зависнуть цикл не может.
Шаблон «первый true» покрывает bound-ы, точки вставки, «первый плохой»; разность bound-ов считает вхождения за O(log n).
stdlib: sort.Search(n, pred), sort.SearchInts (lower bound), slices.BinarySearch → (found, index).
Поиск по ответу — log(range) проверок при монотонном предикате; повёрнутый массив и пик — про локальную монотонность.

🔗 Мостик к Модулю 11

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

← Модуль 9: Куча и приоритетные очереди Модуль 11: Бинарные деревья: обходы и задачи →