Certa vez, recebi o seguinte como uma pergunta de entrevista:

Estou pensando em um número inteiro positivo n. Crie um algoritmo que possa adivinhar em consultas O (lg n). Cada consulta é um número de sua escolha e eu responderei "inferior", "superior" ou "correto"

Este problema pode ser resolvido por uma pesquisa binária modificada, na qual você lista poderes de dois até encontrar um que exceda n e execute uma pesquisa binária padrão nesse intervalo. O que eu acho tão legal nisso é que você pode pesquisar um número infinito de espaços em particular para um número mais rápido do que apenas força brut

A pergunta que tenho, no entanto, é uma ligeira modificação deste problema. Em vez de escolher um número inteiro positivo, suponha que eu escolha um número racional arbitrário entre zero e um. Minha pergunta é: qual algoritmo você pode usar para determinar com mais eficiência qual número racional eu escolhi?

gora, a melhor solução que eu tenho pode encontrar p / q no máximo no tempo O (q) andando implicitamente no Árvore Stern-Brocot, uma árvore de pesquisa binária sobre todos os argumentos. No entanto, eu esperava obter um tempo de execução mais próximo do tempo que obtivemos para o caso inteiro, talvez algo como O (lg (p + q)) ou O (lg pq). Alguém sabe uma maneira de obter esse tipo de tempo de execução?

Inicialmente, considerei usar uma pesquisa binária padrão do intervalo [0, 1], mas isso só encontrará números racionais com uma representação binária não repetitiva, que perde quase todos os racionais. Também pensei em usar outra maneira de enumerar os racionais, mas não consigo encontrar uma maneira de pesquisar nesse espaço, com comparações apenas maiores / iguais / menos.