Сигнал задачи
Когда применять
Есть монотонный предикат или упорядоченная граница.
Что держать в голове
- Уметь поддерживать инвариант закрытого диапазона.
- Уметь избегать переполнения midpoint и зависания границ.
Сложность
- Поиск по индексируемому упорядоченному пространству: O(log n) времени и O(1) памяти в итеративной форме.
Границы и ошибки
- Контракт границ и монотонность предиката важнее формулы mid; смешение закрытого диапазона и полуинтервала вызывает зависание или off-by-one.