我曾经有以下问题作为面试问题：
我正在考虑一个正整数n。提出一种可以在O（lg n）查询中进行猜测的算法。每个查询都是您选择的数字，我将回答“较低”，“较高”或“正确”。
此问题可以通过修改的二进制搜索来解决，在该搜索中，您列出了2的幂，直到找到一个超过n的幂，然后在该范围内运行标准的二进制搜索。我认为这很酷，您可以比蛮力更快地搜索无限数量的特定数字。
不过，我的问题是对此问题的轻微修改。假设我选择一个介于零和一之间的 任意有理数 ，而不是选择一个正整数。我的问题是：您可以使用哪种算法最有效地确定我选择了哪个有理数？
现在，我拥有的最佳解决方案可以在最多O（q）的时间内通过隐式遍历所有有理数的二叉搜索树Stern- Brocot树来找到p / q 。但是，我希望使运行时更接近整数情况下的运行时，例如O（lg（p + q））或O（lg pq）。有人知道获得这种运行时的方法吗？
我最初考虑使用间隔[0，1]的标准二进制搜索，但是这只会找到具有非重复二进制表示形式的有理数，这几乎错过了所有有理数。我还考虑过使用其他方式来列举有理数，但是仅凭比较大/相等/少的比较，我似乎找不到找到这种空间的方法。
好的，这是我仅使用连续分数的答案。
首先让我们在这里获得一些术语。
令X = p / q为未知分数。
令Q（X，p / q）= sign（X-p / q）为查询函数：如果为0，则我们猜到了这个数字；如果它是+/- 1，则告诉我们错误的迹象。
连续分数的常规表示法是A = [a 0 ; a 1，a 2，a 3，… a k ]
= a 0 + 1 /（a 1 + 1 /（a 2 + 1 /（a 3 +1 /（… + 1 / a k）…））））
对于0 <p / q <1，我们将遵循以下算法。
初始化Y = 0 = [0]，Z = 1 = [1]，k = 0。
外循环 ： 先决条件 是：
Y和Z是k + 1项的连续分数，除了在最后一个元素中相差1之外，其余都是相同的，因此Y = [y 0 ; y 1，y 2，y 3，… y k ]和Z = [y 0 ; y 1，y 2，y 3，… y k +1]
（-1）k（YX）<0 <（-1）k（ZX），或更简单地说，对于k个偶数，Y <X <Z，对于k个奇数，Z <X <Y。
在不更改数字值的情况下，将连续分数的度数扩展1步。通常，如果最后一项是y k和y k + 1，我们将其更改为[… y k，y k + 1 =∞]和[… y k，z k + 1 = 1]。现在将k增加1。
内部循环 ：这与@templatetypedef关于整数的采访问题基本相同。我们进行两阶段的二进制搜索以进一步了解：
内环1 ：y k =∞，z k = a，X在Y和Z之间。
Double Z的最后一项：计算M = Z，但m k = 2 * a = 2 * z k。
查询未知数：q = Q（X，M）。
如果q = 0，我们有答案，请转到步骤17。
如果q和Q（X，Y）具有相反的符号，则表示X在Y和M之间，因此将Z = M并转到步骤5。
否则，将Y = M设置为下一步：
内环 2。y k = b，z k = a，并且X在Y和Z之间。
如果a和b相差1，将Y和Z交换，请转到步骤2。
执行二进制搜索：计算M，其中m k = floor（（a + b）/ 2），然后查询q = Q（X，M）。
如果q = 0，则完成操作并转到步骤17。
如果q和Q（X，Y）具有相反的符号，则表示X在Y和M之间，因此设置Z = M并转到步骤11。
否则，q和Q（X，Z）具有相反的符号，这意味着X在Z和M之间，因此设置Y = M并转到步骤11。
完成：X =M。
X = 16/113 = 0.14159292的具体示例
Y = 0 = [0], Z = 1 = [1], k = 0 k = 1: Y = 0 = [0; ∞] < X, Z = 1 = [0; 1] > X, M = [0; 2] = 1/2 > X. Y = 0 = [0; ∞], Z = 1/2 = [0; 2], M = [0; 4] = 1/4 > X. Y = 0 = [0; ∞], Z = 1/4 = [0; 4], M = [0; 8] = 1/8 < X. Y = 1/8 = [0; 8], Z = 1/4 = [0; 4], M = [0; 6] = 1/6 > X. Y = 1/8 = [0; 8], Z = 1/6 = [0; 6], M = [0; 7] = 1/7 > X. Y = 1/8 = [0; 8], Z = 1/7 = [0; 7] --> the two last terms differ by one, so swap and repeat outer loop. k = 2: Y = 1/7 = [0; 7, ∞] > X, Z = 1/8 = [0; 7, 1] < X, M = [0; 7, 2] = 2/15 < X Y = 1/7 = [0; 7, ∞], Z = 2/15 = [0; 7, 2], M = [0; 7, 4] = 4/29 < X Y = 1/7 = [0; 7, ∞], Z = 4/29 = [0; 7, 4], M = [0; 7, 8] = 8/57 < X Y = 1/7 = [0; 7, ∞], Z = 8/57 = [0; 7, 8], M = [0; 7, 16] = 16/113 = X --> done!
在计算M的每个步骤中，间隔范围都会减小。可能很容易证明（尽管我不会这样做），间隔在每一步至少减少了1 / sqrt（5），这表明该算法为O（log q）步。
请注意，这可能与templatetypedef最初的面试问题相结合，并应用对 任何 有理数P / Q，不只是0和1之间，首先计算Q（X，0），然后是正/负整数，连续两次之间的边界整数，然后对小数部分使用上述算法。
接下来，我将发布实现该算法的python程序。
编辑 ：同样，请注意，您不必计算每个步骤的连续分数（这将是O（k），连续分数存在部分近似值，可以计算O（1）中上一步的下一步。 ）
编辑2 ：部分近似的递归定义：
如果A k = [a 0 ; a 1，a 2，a 3，… a k ] = p k / q k，则p k = a k p k-1 + p k-2，q k = a k q k-1 + q K-2。（来源：Niven和Zuckerman，第四版，定理7.3-7.5。另请参见Wikipedia）
示例：[0] = 0/1 = p 0 / q 0，[0; 7] = 1/7 = p 1 / q 1；所以[0; 7，16] =（16 * 1 + 0）/（16 * 7 + 1）= 16/113 = p 2 / q 2。
这意味着，如果两个连续分数Y和Z除了最后一个具有相同的项，并且不包括最后一项的连续分数为p k-1 / q k-1，则可以写成Y =（y k p k- 1 + p k-2）/（y k q k-1 + q k-2）和Z =（z k p k-1 + p k-2）/（z k q k-1 + q k-2）。由此应该可以证明| YZ | 在此算法产生的每个较小的间隔中，它至少减小1 / sqrt（5）倍，但此刻代数似乎超出了我。:-(
这是我的Python程序：
import math # Return a function that returns Q(p0/q0,p/q) # = sign(p0/q0-p/q) = sign(p0q-q0p)*sign(q0*q) # If p/q < p0/q0, then Q() = 1; if p/q < p0/q0, then Q() = -1; otherwise Q()=0. def makeQ(p0,q0): def Q(p,q): return cmp(q0*p,p0*q)*cmp(q0*q,0) return Q def strsign(s): return '<' if s<0 else '>' if s>0 else '==' def cfnext(p1,q1,p2,q2,a): return [a*p1+p2,a*q1+q2] def ratguess(Q, doprint, kmax): # p2/q2 = p[k-2]/q[k-2] p2 = 1 q2 = 0 # p1/q1 = p[k-1]/q[k-1] p1 = 0 q1 = 1 k = 0 cf = [0] done = False while not done and (not kmax or k < kmax): if doprint: print 'p/q='+str(cf)+'='+str(p1)+'/'+str(q1) # extend continued fraction k = k + 1 [py,qy] = [p1,q1] [pz,qz] = cfnext(p1,q1,p2,q2,1) ay = None az = 1 sy = Q(py,qy) sz = Q(pz,qz) while not done: if doprint: out = str(py)+'/'+str(qy)+' '+strsign(sy)+' X ' out += strsign(-sz)+' '+str(pz)+'/'+str(qz) out += ', interval='+str(abs(1.0*py/qy-1.0*pz/qz)) if ay: if (ay - az == 1): [p0,q0,a0] = [pz,qz,az] break am = (ay+az)/2 else: am = az * 2 [pm,qm] = cfnext(p1,q1,p2,q2,am) sm = Q(pm,qm) if doprint: out = str(ay)+':'+str(am)+':'+str(az) + ' ' + out + '; M='+str(pm)+'/'+str(qm)+' '+strsign(sm)+' X ' print out if (sm == 0): [p0,q0,a0] = [pm,qm,am] done = True break elif (sm == sy): [py,qy,ay,sy] = [pm,qm,am,sm] else: [pz,qz,az,sz] = [pm,qm,am,sm] [p2,q2] = [p1,q1] [p1,q1] = [p0,q0] cf += [a0] print 'p/q='+str(cf)+'='+str(p1)+'/'+str(q1) return [p1,q1]
和以下示例输出ratguess(makeQ(33102,113017), True, 20)：
ratguess(makeQ(33102,113017), True, 20)
p/q=[0]=0/1 None:2:1 0/1 < X < 1/1, interval=1.0; M=1/2 > X None:4:2 0/1 < X < 1/2, interval=0.5; M=1/4 < X 4:3:2 1/4 < X < 1/2, interval=0.25; M=1/3 > X p/q=[0, 3]=1/3 None:2:1 1/3 > X > 1/4, interval=0.0833333333333; M=2/7 < X None:4:2 1/3 > X > 2/7, interval=0.047619047619; M=4/13 > X 4:3:2 4/13 > X > 2/7, interval=0.021978021978; M=3/10 > X p/q=[0, 3, 2]=2/7 None:2:1 2/7 < X < 3/10, interval=0.0142857142857; M=5/17 > X None:4:2 2/7 < X < 5/17, interval=0.00840336134454; M=9/31 < X 4:3:2 9/31 < X < 5/17, interval=0.00379506641366; M=7/24 < X p/q=[0, 3, 2, 2]=5/17 None:2:1 5/17 > X > 7/24, interval=0.00245098039216; M=12/41 < X None:4:2 5/17 > X > 12/41, interval=0.00143472022956; M=22/75 > X 4:3:2 22/75 > X > 12/41, interval=0.000650406504065; M=17/58 > X p/q=[0, 3, 2, 2, 2]=12/41 None:2:1 12/41 < X < 17/58, interval=0.000420521446594; M=29/99 > X None:4:2 12/41 < X < 29/99, interval=0.000246366100025; M=53/181 < X 4:3:2 53/181 < X < 29/99, interval=0.000111613371282; M=41/140 < X p/q=[0, 3, 2, 2, 2, 2]=29/99 None:2:1 29/99 > X > 41/140, interval=7.21500721501e-05; M=70/239 < X None:4:2 29/99 > X > 70/239, interval=4.226364059e-05; M=128/437 > X 4:3:2 128/437 > X > 70/239, interval=1.91492009996e-05; M=99/338 > X p/q=[0, 3, 2, 2, 2, 2, 2]=70/239 None:2:1 70/239 < X < 99/338, interval=1.23789953207e-05; M=169/577 > X None:4:2 70/239 < X < 169/577, interval=7.2514738621e-06; M=309/1055 < X 4:3:2 309/1055 < X < 169/577, interval=3.28550190148e-06; M=239/816 < X p/q=[0, 3, 2, 2, 2, 2, 2, 2]=169/577 None:2:1 169/577 > X > 239/816, interval=2.12389981991e-06; M=408/1393 < X None:4:2 169/577 > X > 408/1393, interval=1.24415093544e-06; M=746/2547 < X None:8:4 169/577 > X > 746/2547, interval=6.80448470014e-07; M=1422/4855 < X None:16:8 169/577 > X > 1422/4855, interval=3.56972657711e-07; M=2774/9471 > X 16:12:8 2774/9471 > X > 1422/4855, interval=1.73982239227e-07; M=2098/7163 > X 12:10:8 2098/7163 > X > 1422/4855, interval=1.15020646951e-07; M=1760/6009 > X 10:9:8 1760/6009 > X > 1422/4855, interval=6.85549088053e-08; M=1591/5432 < X p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9]=1591/5432 None:2:1 1591/5432 < X < 1760/6009, interval=3.06364213998e-08; M=3351/11441 < X p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1]=1760/6009 None:2:1 1760/6009 > X > 3351/11441, interval=1.45456726663e-08; M=5111/17450 < X None:4:2 1760/6009 > X > 5111/17450, interval=9.53679318849e-09; M=8631/29468 < X None:8:4 1760/6009 > X > 8631/29468, interval=5.6473816179e-09; M=15671/53504 < X None:16:8 1760/6009 > X > 15671/53504, interval=3.11036635336e-09; M=29751/101576 > X 16:12:8 29751/101576 > X > 15671/53504, interval=1.47201634215e-09; M=22711/77540 > X 12:10:8 22711/77540 > X > 15671/53504, interval=9.64157420569e-10; M=19191/65522 > X 10:9:8 19191/65522 > X > 15671/53504, interval=5.70501257346e-10; M=17431/59513 > X p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1, 8]=15671/53504 None:2:1 15671/53504 < X < 17431/59513, interval=3.14052228667e-10; M=33102/113017 == X
由于Python从一开始就处理biginteger数学，并且此程序仅使用整数数学（区间计算除外），因此它应适用于任意有理数。
编辑3 ：证明这是O（log q）而不是O（log ^ 2 q）的证明纲要：
首先请注意，在找到有理数之前，每个新的连续分数项的步数n k 恰好是 2b（a_k）-1，其中b（a_k）是表示a_k = ceil（log2（a_k） ））：b（a_k）步扩大二进制搜索的“ net”，b（a_k）-1步缩小它。参见上面的示例，您会注意到步骤数始终为1、3、7、15等。
现在，我们可以使用递归关系q k = a k q k-1 + q k-2和归纳法证明所需的结果。
让我们以这种方式陈述它：达到第k个项所需的N k = sum（n k）个步骤之后的q值具有最小值：对于某些固定常数A，c，q> = A * 2 cN。（因此，反过来，我们将得到步骤N的数目<=（1 / c）* log 2（q / A）= O（log q）。）
基本案例：
这意味着A = 1，c = 1/2可以提供所需的界限。实际上，q可能 不会使 每个项加倍（反例：[0; 1，1，1，1，1，1]的增长因子为phi =（1 + sqrt（5））/ 2），所以让我们使用c = 1 / 4。
感应：
因此a k q k-1 > = 2 （N k -1）/ 2 * q k-1 > = 2 （n k -1）/ 2 * A * 2 N k-1 / 4 = A * 2 N k / 4 / sqrt（2）* 2 n k / 4。
Argh-这里最困难的部分是，如果k = 1，则q对于那个项可能不会增加太多，我们需要使用q k-2，但可能比q k-1小得多。
