我曾经得到以下面试问题:
我在想一个正整数n.想出一个可以在O(lg n)查询中猜出它的算法.每个查询都是您选择的数字,我将回答"较低","较高"或"正确".
这个问题可以通过修改后的二进制搜索来解决,在该搜索中,列出2的幂,直到找到超过n的值,然后在该范围内运行标准二进制搜索.我认为这很酷的是,你可以比无限的力量更快地搜索特定数字的无限空间.
不过,我的问题是对这个问题稍加修改.假设我在0和1之间选择一个任意有理数,而不是选择正整数.我的问题是:您可以使用什么算法来最有效地确定我选择的有理数？
现在,我所拥有的最佳解决方案是在最多O(q)时间内通过隐式地走Stern-Brocot树(在所有有理数上的二叉搜索树)中找到p/q .但是,我希望运行时更接近我们为整数情况得到的运行时,可能是O(lg(p + q))或O(lg pq).有没有人知道如何获得这种运行时？
我最初考虑使用区间[0,1]的标准二进制搜索,但这只会找到具有非重复二进制表示的有理数,这几乎错过了所有的有理数.我还想过使用其他一些方法来枚举有理数,但是我似乎找不到一种方法来搜索这个空间给出更大/更小/更少的比较.