algorithm - 算法设计与分析

Question

我陷入了一个问题，我需要解决一个问题，这里是：

编写一个i在数组中找到索引的算法，A[i] = i如果0<=i<=n-1没有找到这样的索引，则返回-1

我及时做了这个问题，O(n)但我的伙伴们说它可以在更短的时间内完成O(lg(n))

谁能帮我找到更好的解决方案？如果是这样，请回复此帖子.. 谢谢

Answer 1

如果数组已排序，那么您可以O(lg(n))使用binary search进行搜索。否则将需要O(n).

Answer 2

如果数组没有排序，这是不可能的。我假设您正在寻找一种确定性的非概率算法。假设存在一个算法“Alg”，它通过访问数组的 O(log(n)) 个单元来解决问题。令 V(I) 是 Alg 在给定输入 I 上访问的一组单元格。还假设输入 I1 的答案是 -1 并且 Alg 正确返回 -1。现在更改 I1 中不在 V(I1) 中的一个单元格，然后再次将其提供给 Alg。当然，Alg 再次返回 -1，这不是正确答案。

Answer 3

您应该对数组进行二进制搜索。你错过了问题陈述的一个非常重要的部分——数组应该提前排序。