Двоичный поиск

Двоичный поиск или бинпоиск (образовано от английского binary) — базовый алгоритм, идеи которого используются в других алгоритмах.

Далее мы рассмотрим различные вариации данной концепции.

Пример детской задачи

Загадано число от $1$ до $100$. Вы можете называть число, в ответ вы получаете ответы <, >, =. Задача, угадать загаданное число за минимальное количество действий.

Это детская задача, возможно вы знаете её решение. Алгоритм по сути является бинпоиском по ответу. Первый раз вы спрашиваете про 50, затем в зависимости от ответа, вы либо заканчиваете играть, или отрезок в котором есть загаданное число сокращается в длине в два раза. Например, искомый отрезок $[1;100]$, после ответа < на вопрос 50, сократится до $[1,50)$.

Так как длина отрезка в котором есть ответ после ответа < или > уменьшается в два раза, то количество вопросов в худшем случае равно $\lceil {\log }_2(100)\rceil$