Если я скажу вам:
«Я думаю о числе от 0 до n, и я скажу вам, является ли ваше предположение высоким или низким», тогда вы сразу же доберетесь до бинарного поиска.
Что если я уберу верхнюю границу? то есть я думаю о положительном целом числе, и вам нужно угадать его.
Один из возможных способов - угадать 2, 4, 8, ..., пока вы не угадаете 2 ** k для некоторого k, и я скажу «ниже». Тогда вы можете применить бинарный поиск.
Есть ли более быстрый метод?
EDIT:
Очевидно, что любое решение займет время, пропорциональное размеру целевого числа. Если я проверю число Грэма через функцию Аккермана, мы подождем некоторое время, какую бы стратегию вы ни преследовали.
Я мог бы предложить и этот алгоритм: угадывайте каждое целое число по очереди, начиная с 1.
Это гарантированно закончится за ограниченное количество времени, но все же это явно намного хуже, чем моя стратегия "полномочия 2". Если я найду худший алгоритм (и знаю, что он хуже), то, может быть, я найду лучший?
Например, вместо степеней 2, может быть, я могу использовать степени 10. Затем я нахожу верхнюю границу с шагом log_10(n) вместо log_2(n) шагов. Но я должен искать больше места. Скажите k = ceil(log_10(n)). Затем мне нужно log_2(10**k - 10**(k-1)) шагов для моего бинарного поиска, который, я думаю, составляет около 10+log_2(k). Для степеней 2 у меня есть примерно log_2(log_2(n)) шагов для фазы поиска. Кто победит?
Что если я буду искать вверх, используя n**n? Или какая-то другая последовательность? Получит ли приз тот, кто сможет найти последовательность, которая растет быстрее всего? Это проблема с ответом?
Спасибо за ваши мысли. И мои извинения тем из вас, кто предложил мне начать с MAX_INT или 2 ** 32-1, так как я явно отдаляюсь от границ практичности здесь.
Окончательное редактирование:
Привет всем,
Спасибо за ваши ответы. Я принял ответ Нормана Рэмси (и еще одного комментатора) для того, что я понял следующим аргументом: для целевого числа n любая стратегия должна быть способна различать (по крайней мере) числа от 0..n, что означает вам нужно (как минимум) O (log (n)) сравнений.
Однако некоторые из вас также указали, что проблема не является четко определенной, во-первых, потому что невозможно выбрать «случайное положительное целое число» при равномерном распределении вероятности (или, скорее, равномерное распределение вероятности не может существовать над бесконечным множеством). И как только я дам вам неравномерное распределение, вы можете разделить его пополам и применить бинарный поиск как обычно.
Это проблема, о которой я часто размышлял, когда ходил, поэтому я рад получить два убедительных ответа на нее.