面试问题 - 在有序阵列型X搜索索引i使得X [我] =我 [英] Interview question - Search in sorted array X for index i such that X[i] = i

问题描述

我提出以下问题在我昨天采访：

I was asked the following question in my interview yesterday:

考虑一个Java或C ++数组说 X 这是排序，并没有在它的两个元素是一致的。如何最好的，你可以找到一个索引说我该索引的，这样的元素也是我。这就是 X [我] =我。

Consider a Java or C++ array say X which is sorted and no two elements in it are same. How best can you find an index say i such that element at that index is also i. That is X[i] = i.

由于澄清，她也给了我一个例子：

As clarification she also gave me an example:

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

      Answer is 3 as X[3] = 3.

我能想到的最好的是线性搜索。经过采访我，虽然有很多关于这个问题，但找不到任何更好的解决方案。我的论点是：具有所需性能的元素可以在阵列中的任何地方。因此，也有可能是在阵列的最末端，所以我们需要检查每一个元素。

The best I could think was a linear search. After the interview I though a lot on this problem but could not find any better solution. My argument is: the element with the required property can be anywhere in the array. So it could also be at the very end of the array so we need to check every element.

我只是想从社区，以确认在​​这里，我是对的。请告诉我，我是正确的：）

I just wanted to confirm from the community here that I'm right. Please tell me I'm right :)

感谢

推荐答案

这可以在完成O（logN）的时间和 0（1 ）用略加修改二进制搜索的空间。

This can be done in O(logN) time and O(1) space by using a slightly modified binary search.

考虑一个新的数组是，使得 Y [i] = X [I] - 我

Consider a new array Y such that 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 元素是增加的顺序，在元素 新的数组是将在非减的顺序。因此，一个二进制 搜索的 0 在是将给出答案。

Since the elements in X are in increasing order, the elements in the new array Y will be in non-decreasing order. So a binary search for 0 in Y will give the answer.

但是创建是将 O（N）的空间和 O（N） 的时间。因此，而不是 创建新的数组，你只需要修改的二进制搜索，使得 参照 Y [I] 替换 X [I] - 我

But creating Y will take O(N) space and O(N) time. So instead of creating the new array you just modify the binary search such that a reference to Y[i] is replaced by 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 ++实现

Java implementation

C++ implementation

这篇关于面试问题 - 在有序阵列型X搜索索引i使得X [我] =我的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！