具有递增整数数组的高效算法

Question

我一直在自学自己的数据结构在python中,不知道我是否过度思考(或解密!)以下问题:

• 我的目标是提出一种有效的算法

• 使用该算法,我的目标是确定是否存在整数,使得A [i] = i在增加的整数数组中

• 然后我想找到大O符号的运行时间作为n的长度的函数？

所以这不会只是O(log n)的略微修改版本,其功能相当于:f(i)= A [i] - i.我读这个问题错了吗？任何帮助将不胜感激!

Answer 1

注意1：因为你说整数在增加，所以你已经排除了数组中存在重复项（否则你会说单调增加）。因此，可以快速检查第一个元素是否大于 1，以排除是否无解。换句话说，为了有任何解的机会，第一个元素必须 <= 1。

注2：与注1类似，如果最后一个元素<数组长度，则无解。

一般来说，我认为你能做的最好的事情就是二分搜索。您将其捕获在低指数和高指数之间，然后检查低指数和高指数之间的中间指数。如果 array[middle] 等于 middle，则返回 yes。如果小于middle，则将left设置为middle+1。否则，将 right 设置为 middle - 1。如果 left 变为 > right，则返回 no。

运行时间为 O( log n )。

编辑：如果允许单调递增，算法将不起作用。练习：解释原因。:-)