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