增加整数数组的有效算法

Question

我一直在用python自学自己的数据结构，不知道自己是在思考过虑(还是在思考不足！)以下问题：

• 我的目标是想出一种高效的算法
• 使用该算法，我的目标是确定一个整数i是否存在于一个不断增加的整数数组中。
• 然后，我想找出运行时间的大-O符号，作为一个函数n的长度A？

那么，这不是一个稍微修改过的O(log )版本，它的函数等价于: f( i ) = Ai。我看错了这个问题吗？任何帮助都将不胜感激！

Answer 1

注1:因为你说整数在增加，所以你已经排除了数组中有重复项(否则你会说单调增加)。因此，如果第一个元素大于1，就可以快速检查是否没有解决方案。换句话说，要有任何解决方案的可能性，第一个元素必须是<= 1。

注2:类似于Note 1，如果最后一个元素是<数组的长度，那么就没有解决方案。

一般来说，我认为你能做的最好的就是二进制搜索。你把它夹在低指数和高指数之间，然后检查低指数和高指数之间的中间指数。如果数组中间等于中间，则返回是。如果小于中间，则设置为middle+1。否则，将右设置为中间1。如果左变为>右，则返回否。

运行时间为O( log )。

编辑:算法不工作，如果你允许单调增长。运动:解释原因。:-)

Answer 2

• 你说得对。在您的i大小的数组中找到一个元素O(Log A)确实是O(Log A)。
• 但是，您可以做得更好:如果您将内存复杂性转换为时间复杂性，O(Log A) -> O(1)就会做得更好，这就是“优化器”倾向于做的。

我的意思是:如果将新数组元素插入到“高效”哈希表中，则可以在恒定时间O(1)中实现find函数

这在很大程度上取决于您要插入的元素：

• 它们很独特吗？想想碰撞
• 你多长时间一次insert

Answer 3

这是一个有趣的问题:-)

您可以使用二分法来定位a[i] == i所在的位置

       0  1  2  3  4  5  6
a = [-10 -5  2  5 12 20 100]

When i = 3,   i < a[i],  so bisect down
When i = 1    i > a[i],  so bisect up
When i = 2    i == a[i], you found the match

运行时间为O(log )。