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

Question

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

考虑一个 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.

我能想到的最好的方法是线性搜索。面试后我虽然对这个问题说了很多，但找不到更好的解决方案。我的论点是:具有所需属性的元素可以在数组中的任何位置。所以它也可能在数组的最后，所以我们需要检查每个元素。

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

Answer 1

这可以在 O(logN) 时间和 O(1) 空间内完成，方法是使用稍微修改的 binary search .

考虑一个新数组 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中的元素都是递增顺序的，所以X中的元素 新数组 Y 将按 非递减 顺序排列。所以一个二进制 在 Y 中搜索 0 将给出答案。

但是创建 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 implementation

C++ implementation