algorithm - 查找任意大数的算法

我一直在想：假设你有一个无穷大的数字，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似乎是个坏主意。
这只是我一直在想的事情，我想听听别人怎么想

最佳答案

像通常的“猜我的号码”游戏一样使用二进制搜索。但是由于没有有限的上端点，我们做了第一个阶段来寻找合适的上端点：
最初，任意设置上端点（例如1000000，尽管1或1^100也可以工作——给定要工作的无限空间，所有有限值都同样不成比例）。
将神秘数字X与上限点进行比较。
如果不够大，加倍，再试一次。
一旦上限点大于神秘数字，继续进行正常的二进制搜索。
第一阶段本身类似于二进制搜索。不同的是，不是每一步都把搜索空间减半，而是加倍每个阶段的成本都是O(log X)一个小的改进是在每一个倍增步骤中设置下端点：我们知道X至少与上一个上端点一样高，因此我们可以将其作为下端点重用。搜索空间的大小仍然是每一步的两倍，但最终将是原来的一半大二进制搜索的成本将减少1步，因此它的整体复杂度保持不变。
一些注释
以下是对其他评论的回应：
这是一个有趣的问题，计算机科学不仅仅是关于在物理机器上可以做什么。只要这个问题能被正确地定义，它就值得我们去问和思考。
数字的范围是无限的，但任何可能的神秘数字都是有限的所以上面的方法最终会找到它。最终定义为，对于任何可能的有限输入，算法将在有限步数内终止。但是，由于输入是无限的，因此步骤的数量也是无限的（只是，在每种特定情况下，它都将“最终”终止）。

关于algorithm - 查找任意大数的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9970339/