寻找任意大数的算法

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至少与前一个上端点一样高，所以我们可以重用它作为下端点。搜索空间的大小在每一步都会翻一番，但最终将是原来的一半。二进制搜索的成本将仅减少1步，因此其总体复杂度保持不变。

一些笔记

以下是对其他评论的几点回应：

这是一个有趣的问题，计算机科学不仅仅是关于可以在物理机器上做什么。只要这个问题能被正确定义，它就是值得询问和思考的。

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

Answer 2

如果我对你的问题理解正确(如果我不理解，请告诉我)，你是在问如何解决“从1到10中选择一个数字”的问题，只是上限是无穷大而不是10。

如果你的数字空间真的是无限的，那么以下就是真的：

• 该值将永远不会保存在任何物理硬件上的int (或任何其他数据类型)中您将永远不会找到您的编号

如果空间非常大，但又很有限，我认为最好的方法是二进制搜索。从数字范围的中间开始。如果想要的数字更高或更低，则将该数字空间的一半分成两半，然后重复进行，直到找到所需的数字。

在您建议的实现中，您引发了y ^ c。然而，无论选择多大的c，它都不会在无限空间中移动指针。

Answer 3

无穷大不是一个数字。因此，即使使用计算机，您也找不到它。