我是新来的。作为一名研究生，我已经对算法进行了一段时间的头脑 Storm 。我感谢任何可以扩展的关于以下问题的帮助。我已经进行了足够的搜索，但找不到解决此问题的任何解决方案。
我们有一个无限长的已排序不同数字数组。前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))。
请发表您的看法。谢谢
最佳答案
您确实可以通过指数搜索解决无限数组的问题，即不知道 m。
尝试第一个元素并将索引加倍，直到得到 1。这将花费 O(Lg n) 步。然后你切换到二进制搜索并在额外的 O(Lg n) 步中得到答案。
k 的值无关紧要。
这种方法在现实世界中是有意义的，即对于一个有限但大小未知的数组，前提是至少有一半的数组被 1 填充，以便搜索在边界内终止。
关于arrays - 分而治之算法(二分查找的应用？!)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28395920/