монотонный предикат

EN: monotonic predicate

Булева функция f(x), меняющая значение не более одного раза при росте x — с false на true или с true на false. Бинарный поиск требует монотонного предиката: как только f(x) становится true, она остаётся true для всех больших x, поэтому границу можно найти за O(log n) шагов.