分治算法（二分查找的应用？！）

Question

我是新来的。作为一名研究生，我已经思考了一段时间的算法。我非常感谢任何能够帮助解决以下问题的帮助。我已经进行了足够的搜索，但没有找到与该问题相近的解决方案。

我们有一个无限长的排序不同数字数组。前n个数字是大于0但小于1的分数。所有其余元素都是“1”，您不知道n的值。您需要开发一种算法来检查用户给定的分数F是否出现在该数组中。分析您的算法作为n的函数的时间复杂度。（例如，对于n = 8的示例，其中“1”开始在数组的第8个位置）

我的方法： 我猜想解决此问题的最佳方法是使用二分查找。每次我们都可以将数组大小缩小一半，最终到达要找的分数。假设数组中有m个元素，包括“1”。分数元素的数量为n。 在整个数组上执行二分搜索的时间复杂度为O(log(m))。由于被要求以n的形式表达时间复杂度，因此m=n+k（假设数组中的“1”的数量为k）。 因此，这个问题的时间复杂度为O(log(n+k))。

请分享您的想法。谢谢

- whyme

---

我们有一个排序且不重复的数字数组，长度是无限长。停止操作，立即离开计算机科学系，前往隔壁的数学系。 - Mike Nakis

@MikeNakis 为什么？一些计算机科学算法需要假设未绑定的值。 - ElderBug

你无法创建一个长度为无限的数组。你可以谈论一个无尽的物品流，但不能称之为无限数组。当然，在一个物品流上你也无法执行二分查找，因为你需要知道总共有多少项才能计算中间项，等等。 - Mike Nakis

这些数字已经排序了吗？ - user1196549

不确定是否应该关闭为重复，但是这个问题基本上是“在无限长度的排序数组中查找元素”的一个特例。 - amit

Answer 1

你确实可以用指数搜索方法解决无限数组的问题，即不知道m的情况。

从第一个元素开始尝试，并将索引翻倍直到获得1。这需要O(Lg n)步骤。然后您切换到二进制搜索，在额外的O(Lg n)步骤中获得答案。

K的值并不重要。

这种方法在现实世界中也是可行的，即对于具有有限但未知大小的数组，只要数组的至少一半填充为1，搜索就会在范围内终止。

- user1196549

---

在实践中，您甚至不会在指数搜索中到达1，而只会到第一个大于F的元素。然后，您只需要在该位置和前一个位置之间执行二进制搜索。当然，这不会影响最坏情况下的时间复杂度，但可能会给您带来更好的平均情况。 - biziclop

谢谢。很有道理 :) - whyme

@biziclop：没错。复杂度实际上是O（Lg i），其中i是所搜索元素的索引。另外，我并没有说二分查找必须从第一个元素开始 :) 但这种优化并不会改善平均情况，仍然是O（Lg n）或O（Lg i），它只是节省了一次测试。 - user1196549

Answer 2

二分查找适用于已排序的数组。如果您的小数位于0和1之间，则您的数组已排序，因此可以在整个数组上执行二分查找，并且它的复杂度为O（lg（n + k）），其中n和k是您在问题中提到的值。无论如何，您的数组可能非常大，而小数的数量可能很少。因此，无论时间复杂度如何，在这种情况下顺序搜索将更快。

因此，在您的情况下，我建议使用简单的顺序搜索，其复杂度为O（n）。

- noname

---

问题在于你不知道n的值。尝试理解Yves Daoust的答案/指数搜索。 - greybeard

是的。但如果值在区间<0,1>内且已排序，并且数组的“空”元素具有值1，那么您就知道何时停止-当您到达第一个具有值1的元素时！因此，顺序搜索仍将具有复杂度O（n），其中n是数组中的元素数量。 - noname