面试问题 - 在排序数组 X 中搜索索引 i 使得 X[i] = i [英] 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，它是经过排序的，并且其中没有两个元素是相同的.您如何最好地找到一个索引，例如 i，以便该索引处的元素也是 i.那就是 X[i] = i.

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) 时间和 O(1) 空间通过使用一个稍微修改了二进制搜索.

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

考虑一个新数组 Y 使得 Y[i] = X[i] - 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中的元素是递增的顺序，所以新数组 Y 将按 非递减 顺序排列.所以一个 二进制在 Y 中搜索 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.

但是创建 Y 需要 O(N) 空间和 O(N) 时间.所以代替创建新数组，您只需修改二进制搜索，以便对 Y[i] 的引用被替换为 X[i] - 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++ 实现

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