Представьте, что у нас есть набор целых чисел.Мы этого не знаем, единственное, что мы знаем, это то, что каждое число лежит в интервале [0, MAX), и, очевидно, числа не повторяются.Затем нам нужно найти множество.Нам разрешается назвать целое число, а затем нам говорят число в наборе, которое меньше или равно числу, которое мы выбрали, и ближе всего к нему.Наша цель - найти набор с минимальным количеством попыток.
Например, пусть у нас есть набор [0, 7, 8, 1000] и MAX == 10000.Пусть TRY - функция, которую мы можем использовать.Тогда TRY (4) == 0, TRY (7) == 7, TRY (8) == 8, TRY (555) == 8 и TRY (7777) == 1000.Затем мы должны убедиться, что мы не пропустили число, поэтому мы должны попробовать много других чисел.
Вопрос в том, какой алгоритм поиска наиболее эффективен.Пробовать каждое число в интервале, очевидно, плохо.Может быть, нам следует попробовать алгоритм, подобный бинарному поиску, который исключает наборы, в которых гарантированно не должно быть чисел (TRY (7777) == 1000, поэтому в (1000, 7777]) нет чисел.ответ.