ды я получил следующий вопрос в качестве интервью:

Я думаю о положительном целом числе n. Придумайте алгоритм, который может угадать его в O (LG N) запросах. Каждый запрос является числом по вашему выбору, и я отвечу либо «ниже», «выше» или «правильно».

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

Вопрос, который у меня есть, является небольшой модификацией этой проблемы. Вместо того, чтобы выбрать положительное целое число, предположим, что я выбираюпроизвольное рациональное число между нулем и единицей. У меня вопрос: какой алгоритм вы можете использовать, чтобы наиболее эффективно определить, какое рациональное число я выбрал?

Прямо сейчас, лучшее решение, которое у меня есть, может найти p / q в самое большее время O (q), неявно пройдяСтерн-Броко, бинарное дерево поиска по всем рациональным. Тем не менее, я надеялся получить время выполнения ближе к времени выполнения, которое мы получили для целочисленного случая, возможно, что-то вроде O (lg (p + q)) или O (lg pq). Кто-нибудь знает способ получить такой вид времени выполнения?

Первоначально я рассмотрел использование стандартного двоичного поиска в интервале [0, 1], но это позволит найти только рациональные числа с неповторяющимся двоичным представлением, в котором пропущены почти все рациональные числа. Я также подумал об использовании какого-то другого способа перечисления рациональных чисел, но я не могу найти способ поиска в этом пространстве, просто сравнивая больше / равно / меньше.