面试问题 - 在排序数组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.

我能想到的最好的是线性搜索.在采访之后我虽然在这个问题上做了很多但却找不到更好的解决方案.我的论点是:具有required属性的元素可以在数组中的任何位置.所以它也可能在数组的最后,所以我们需要检查每个元素.

我只想在这里向社区证实我是对的.请告诉我我是对的:)

谢谢

Answer 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将在非递减顺序.因此,一个二进制搜索为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++实现

Answer 2

有一些更快的解决方案,平均O(log n)或在某些情况下O(log log n)而不是O(n).有一个谷歌的"二分搜索"和"插值搜索",你可能会找到很好的解释.

如果数组未排序,那么是,该元素在任何地方,你不能得到O(n),但不是排序数组的情况.

-

根据要求对插值搜索的一些解释:

虽然二分搜索仅涉及以"更大/更大"的方式比较两个元素,但插值搜索也试图使用数值.要点是:你有一个从0到20000的值的排序范围.你寻找300 - 二进制搜索将从范围的一半开始,为10000.插值搜索猜测300可能会接近0超过20000,所以它会首先检查元素6000而不是10000.然后再次 - 如果它太高,递归到较低的子范围,并且它太低 - 递归到较高的子范围.

对于具有+ - 均匀分布值的大数组,插值搜索应该比二进制搜索快得多 - 编码并自己查看.此外,如果首先使用一个插值搜索步骤,然后使用一个二进制搜索步骤,则效果最佳,依此类推.

请注意,在字典中查找某些内容时,这是人类直观的事情.

Answer 3

它不需要考虑任何阵列方面Y为建议的答案被@codaddict.

使用二进制搜索并检查给定数组的中间元素,如果它低于其索引,那么我们不需要检查任何较低的索引,因为数组是排序的,所以如果我们向左移动,减去m个索引和(至少)m值,所有后续元素也将太小.例如,如果arr[5] = 4再arr[4] <= (4 - 1)和arr[3] <= (4 - 2)等.如果中间元素大于其索引,则可以应用类似的逻辑.

这是简单的Java实现:

int function(int[] arr) {
        int low = 0;
        int high = arr.length - 1;

        while(low <= high) {
            int mid = high - (high - low) / 2;

            if(arr[mid] == mid) {
                 return mid;
            } else if(arr[mid] < mid) {
                 low = mid + 1;
            } else {
                 high = mid - 1;
            }
        }

        return -1; // There is no such index
}

请注意,只有所有元素都不同,上述解决方案才有效.

Answer 4

我认为这会更快.

从列表中间开始

如果X [i]> i然后转到剩余左侧的中间

如果X [i] <i然后走到剩下的中间

继续这样做,它会将每个循环中可能元素的数量减少一半