找到任意大数的算法

Question

这是我一直在考虑的事情:假设你有一个数字,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似乎是个坏主意.

这只是我一直想知道的事情,我想听听其他人的想法

Answer 1

使用二进制搜索,就像通常的"尝试猜测我的号码"游戏一样.但由于没有有限的上限点,我们会在第一阶段找到合适的上端点:

• 最初任意设置上端点(例如1000000,尽管1或1 ^ 100也可以工作 - 给定无限空间工作,所有有限值同样不成比例).
• 将神秘数字X与上端点进行比较.
• 如果它不够大,请加倍,然后再试一次.
• 一旦上端点大于神秘数字,继续进行正常的二进制搜索.

第一阶段本身类似于二元搜索.不同之处在于,不是每一步都将搜索空间减半,而是将其翻倍!每个阶段的成本是O(log X).一个小的改进是在每个加倍步骤设置低端点:我们知道X至少与前一个高端点一样高,所以我们可以将它重用为低端点.搜索空间的大小在每一步仍然翻倍,但最终它将是原来的一半.二进制搜索的成本将仅减少一步,因此其总体复杂性保持不变.

一些笔记

回应其他评论的几点说明:

这是一个有趣的问题,计算机科学不只是关于物理机器上可以做什么.只要问题可以正确定义,就值得提出并思考.

数字范围是无限的,但任何可能的神秘数字都是有限的.所以上面的方法最终会找到它. 最终定义为,对于任何可能的有限输入,算法将在有限数量的步骤内终止.然而,由于输入是无限制的,步骤的数量也是无限的(只是在每种特定情况下,它将"最终"终止.)