Условие
В системе мониторинга хранится параметр конфигурации, значение которого является целым числом от 1 до 100. Это значение известно системе, но неизвестно инженеру.
Чтобы определить число, инженер может отправлять в систему запрос-проверку с предполагаемым значением параметра. После каждого запроса система отвечает одним из трех сообщений:
- «больше» — значение параметра больше указанного;
- «меньше» — значение параметра меньше указанного;
- «верно» — параметр угадан.
Из-за ограничений системы допускается не более семи запросов.
Задача
Разработайте стратегию запросов, которая гарантированно определит значение параметра — целое число от 0 до 100 — не более чем за семь попыток.
Решение
На первый взгляд кажется, что найти одно число из 100 за такое количество попыток невозможно. Однако в этой задаче нужно вспомнить, как устроен бинарный поиск.
Числа от 0 до 100 — это отсортированный массив. На каждом шаге берем середину диапазона. Если число меньше, ищем в правой половине диапазона, если больше — в левой. Повторяем, пока не найдем нужное число или диапазон не исчезнет.
Допустим, значение параметра равняется 51. Порядок действий будет таким.
- Разбиваем диапазон от 0 до 100 и находим середину. Отправляем запрос: это число 50? Ответ: «больше». Значит, ищем среди вариантов от 51 до 100.
- Вновь берем середину диапазона: это число 75? Ответ: «меньше». Ищем от 51 до 74.
- Продолжаем: это число 62? Ответ: «меньше». Вместо 62 должно было быть 62.5, но по условию числа могут быть только целыми, поэтому округлим в меньшую сторону. Далее ищем от 51 до 61.
- Это число 56? Ответ: «меньше». Ищем от 51 до 55.
- Это число 53? Ответ: «меньше». Ищем от 51 до 52.
- Это число 52? Ответ: «меньше». Остается 51.
- Это число 51? Ответ: «верно».
Подобный порядок действий можно написать для любого числа.
