面试问题-在排序数组X中搜索索引i，使得X [i] = i

一尘不染

面试问题-在排序数组X中搜索索引i，使得X [i] = i

algorithm

昨天在面试中被问到以下问题：

考虑一个Java或C ++数组X，该数组被排序并且其中没有两个元素相同。您如何才能最好地找到一个索引，说i该索引上的元素也是i。那是X[i] = i。

为了澄清起见，她还举了一个例子：

Array X : -3 -1 0 3 5 7
index   :  0  1 2 3 4 5

Answer is 3 as X[3] = 3.

我认为最好的是线性搜索。面试后，尽管我对这个问题有很多看法，但找不到更好的解决方案。我的观点是：具有required属性的元素可以在数组中的任何位置。因此它也可能位于数组的最后，因此我们需要检查每个元素。

我只是想从这里的社区确认我是对的。请告诉我我是对的:)

阅读 255

2020-07-28

共1个答案

一尘不染

通过使用稍微修改的二进制搜索，可以在O(logN)时间和O(1)空间上完成此操作。

考虑一个新的数组Y，这样Y[i] = X[i] - i

Array X : -3 -1   0  3  5  7
index   :  0  1   2  3  4  5
Array Y : -3 -2  -2  0  1  2

由于元件在X处于增加顺序，新的数组中的元素Y将在 非递减 顺序。因此，对in 进行 二进制搜索 将给出答案。0``Y

但是创造Y将需要时间O(N)和空间O(N)。因此，您无需修改新的数组，只需修改二进制搜索，以Y[i]替换对的引用X[i] - i。

算法：

function (array X) 
       low  = 0
       high = (num of elements in X) - 1

       while(low <= high) 
               mid = (low + high) / 2

               // change X[mid] to X[mid] - mid
               if(X[mid] - mid == 0)
                       return mid

               // change here too
               else if(X[mid] - mid < 0)
                       low = mid + 1;

               else
                       high = mid - 1;
       end while

       return -1 // no such index exists...return an invalid index.

end function

Java实现

C ++实现

2020-07-28