Разделяй и властвуй или как угадать число от 1 до 1000 за 10 вопросов?

Однажды великий мудрец молвил: «Я загадал число от 1 до 1000. Ты можешь задавать вопрос, на который можно ответить только «да» или «нет». За сколько вопросов угадаешь загаданное число?». Ответ поразил всех!

А действительно, за сколько? Предположим, что мы пока что задаем неумелый вопрос: «Твое число равно x?», где x — число, которое мы пытаемся угадать. За сколько вопросов мы угадаем исходное число?

Если мы рассмотрим худший случай и представим себя в роли самого невезучего человека в истории, то мы всегда будем промахиваться мимо нашего числа и дойдем до него только в самую последнюю попытку. Она будет тысячной по счету!

Возможно ли это? Вполне. Особенно в программировании. Да, мы можем и угадать с первого раза наше число, но мы сейчас говорим в контексте программирования, где при хорошо составленных тестах такой алгоритм отработает худшим образом, а именно – линейно.

Если бы загадывали число от 1 до n, то в худшем случае нам потребовалось бы n попыток. Таким образом, мы сделали линейный поиск с временной сложностью $O(n)$.

Теперь научимся задавать более правильные вопросы.

У нас лишь одно загаданное число – так давайте попробуем угадать, в какой части оно находится: до середины или после середины. Зная, где оно находится, мы можем вовсе не рассматривать вторую рассматриваемую половину.

Приведем пример, пусть загадали число 92. Тогда диалог будет выглядеть примерно так:

1. Загаданное число не превышает 500?
– Да
Тогда стоит рассматривать отрезок $[$1, 500$]$, а отрезок $[$501, 1000$]$ не подойдет.

2. Загаданное число не превышает 250?
– Да
Аналогично рассматриваем теперь отрезок $[$1, 250$]$.

3. Загаданное число не превышает 125?
– Да

4. Загаданное число не превышает 62?
– Нет (= превышает)
Тогда слева от 62 нас ничего не интересует и теперь рассмотрим правую часть – отрезок $[$62, 125$]$.

5. Загаданное число не превышает 93? (середина между 62 и 125)
– Да

6. Загаданное число не превышает 77?
– Нет

7. Загаданное число не превышает 85?
– Нет

8. Загаданное число не превышает 89?
– Нет

9. Загаданное число не превышает 91?
– Нет

10. (на текущий момент у нас отрезок $[$91, 93$]$). Загаданное число не превышает 92?
– Да

11. (сейчас отрезок $[$91, 92$]$). Загаданное число не превышает 91?
– Нет

Теперь мы однозначно знаем, что ответ 92. Таким образом, мы нашли ответ за 11 вопросов.
А если бы загадали число от 1 до n? За сколько вопросов можно было бы угадать число?

На самом деле количество вопросов сводится к двоичному логарифму от n. Что это за зверь такой? Проще говоря, нам нужно найти такую степень двойки, которая не превышает n. Для 1000 это будет 10, потому что $2^{10} = 1024$. У нас получилось 11 вопросов, потому что середина отрезка вычислялась с округлением вниз, и от округлений появился дополнительный вопрос на маленьких длинах отрезка. Это влияет на количество вопросов совсем незначительно.

Сейчас мы искали загаданное число с помощью двоичного (бинарного) поиска с временной сложностью $O(log(n))$.

Чтобы понять, насколько это быстрее, чем линейный поиск, можно просто оценить это на разных числах, особенно на больших. Рассмотрим количество заданных вопросов с помощью этих двух методов при разных n:

Вместо миллиарда вопросов мы зададим всего 30!

Это колоссальная разница в скорости, которая позволяет искать что-либо в отсортированной последовательности практически моментально. Поэтому не перебирайте числа вслепую, а используйте алгоритмы!

Помимо конкретного числа с помощью бинарного поиска можно делать еще много всего:

• искать позиции чисел (первую, последнюю) в массиве
• искать слово в словаре
• строки в матрице
• и еще многое другое.

А сколько всего можно делать с помощью бинарного поиска по ответу – это уже вопрос для другой статьи.
Хотите продолжения?