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

Interview question - Search in sorted array X for index i such that X[i] = i

提问by John

I was asked the following question in my interview yesterday:

我昨天面试的时候被问到以下问题：

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

考虑一个 Java 或 C++ 数组，说明X哪个已排序并且其中没有两个元素是相同的。您如何最好地找到一个索引i，说明该索引处的元素也是i. 那就是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 :)

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

采纳答案by codaddict

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

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

Consider a new array Ysuch that Y[i] = X[i] - i

考虑一个新数组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

Since the elements in Xare in increasingorder, the elements in the new array Ywill be in non-decreasingorder. So a binary searchfor 0in Ywill give the answer.

由于元件在X处于增加顺序，新的数组中的元素Y将在非递减顺序。所以对in的二分搜索将给出答案。0Y

But creating Ywill 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.

但是创造Y需要O(N)空间和O(N)时间。因此，而不是创建新的数组你刚才修改的二进制搜索使得参照Y[i]所取代X[i] - i。

Algorithm:

算法：

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

Java实现

C++ implementation

C++ 实现

回答by Kos

There are some faster solutions, averaging O(log n) or in some cases O(log log n) instead of O(n). Have a google for "binary search"and "interpolation search", you're likely to find very good explanations.

有一些更快的解决方案，平均 O(log n) 或在某些情况下 O(log log n) 而不是 O(n)。用谷歌搜索“二进制搜索”和“插值搜索”，你很可能会找到很好的解释。

If the array is unsorted, then yes, the element is anywhere and you can't get under O(n), but that's not the case with sorted arrays.

如果数组是未排序的，那么是的，元素在任何地方，并且不能低于 O(n)，但排序数组不是这种情况。

--

——

Some explanation on interpolation search as requested:

根据要求对插值搜索进行一些解释：

While the binary search only concerns with comparing two elements in terms of "greater / not greater", the interpolation search tries to also make use of numerical values. The point is: You have a sorted range of values from 0 to, say, 20000. You look for 300 - binary search would start at the half of range, at 10000. The interpolation search guesses that 300 would probably be somewhere closer to 0 than 20000, so it would check the element 6000 first instead of 10000. Then again - if it's too high, recurse into lower subrange, and it's too low - recurse into upper subrange.

虽然二分搜索仅涉及根据“更大/不更大”比较两个元素，但插值搜索也尝试使用数值。关键是：你有一个从 0 到 20000 的排序范围。你寻找 300 - 二分搜索将从范围的一半开始，在 10000。插值搜索猜测 300 可能更接近于 0比 20000，所以它会首先检查元素 6000 而不是 10000。然后再次 - 如果它太高，递归到下子范围，它太低 - 递归到上子范围。

For a big array with +- uniform distribution of values, interpolation search should behave much faster than binary search - code it and see for yourself. Also, works best if first you use one interpolation search step, then one binary search step, and so on.

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

Note that it's the thing a human does intuitively when looking up something in a dictionary.

请注意，这是人类在字典中查找内容时凭直觉所做的事情。

回答by Mor Shemesh

You can perform a binary search: search the middle, if the value is lower than the index, than no lower index will contain the same value.

您可以执行二分查找：搜索中间值，如果值低于索引，则没有更低的索引将包含相同的值。

Then you search the higher half, and continue till you find the element, or reach one element span.

然后搜索上半部分，并继续直到找到该元素，或达到一个元素跨度。

回答by thecoshman

of the top of my head, doing binary splitting might be faster.

在我的头顶上，进行二进制拆分可能会更快。

look at the middle value, if it is high then what you need, re-search in the lower half.

看看中间值，如果它高那么你需要什么，在下半部分重新搜索。

After one comparison, you have already spilt your data set in half

经过一次比较，你已经把你的数据集一分为二了

回答by JOTN

I think this would be faster.

我认为这会更快。

Start in the middle of the list

从列表中间开始

If X[i] > i then go to the middle of the remaining left side

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

if X[i] < i then go the middle of the remaining right

如果 X[i] < i 然后去剩下的右边的中间

Keep doing that and it will reduce the number of possible elements by half for each loop

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

回答by skimobear

After reading the question it seems like there is one scenario that can be used to speed up the lookup. When comparing the position to the value, if the value is greater then the position then the value can be used as the next position to evaluate. This will help jump through the array faster. This can be done because the array is sorted. The values that we are skipping are conceptually shifted to the left in the array and are in the wrong location.

阅读问题后，似乎有一种场景可用于加快查找速度。将位置与值进行比较时，如果值大于该位置，则该值可用作下一个要评估的位置。这将有助于更快地跳过阵列。这是可以完成的，因为数组已排序。我们跳过的值在概念上被移到了数组的左边，并且位置错误。

Example:

例子：

int ABC[] = { -2, -5, 4, 7, 11, 22, 55 };

If my current position is 2 and it has a value of 4 they are not equal and conceptually the value 4 is shifted to the left. I can use the value of 4 as my next position because if the value 4 is out of position then everything less then 4 is out of position as well.

如果我当前的位置是 2 并且它的值为 4，它们就不相等，并且从概念上讲，值 4 向左移动。我可以使用值 4 作为我的下一个位置，因为如果值 4 处于不利位置，那么小于 4 的所有内容也处于不利位置。

Some example code just for the sake of discussion:

一些示例代码只是为了讨论：

void main()
{
    int X[] = { -3, -1, 0, 3, 5, 7};
    int length = sizeof(X)/sizeof(X[0]);

    for (int i = 0; i < length;) {
        if (X[i] > i && X[i] < length)
            i = X[i];                 // Jump forward!
        else if (X[i] == i) {
            printf("found it %i", i);
            break;
        } else
            ++i;
    }
}

回答by NirmalGeo

Modified version of Binary Search would suffice I guess

我猜二进制搜索的修改版本就足够了

Suppose the sequence is

假设序列是

Array : -1 1 4 5 6
Index :  0 1 2 3 4

Result : 1

or

或者

Array : -2 0 1 2 4 6 10
Index :  0 1 2 3 4 5 6 

Result: 4

From both the examples we see that the required result will never lie on the right side if mid < a[mid]... pseudocode would look something like this

从这两个示例中我们看到，如果 mid < a[mid]... 伪代码看起来像这样，则所需的结果永远不会位于右侧

mid <- (first + last )/2

if a[mid] == mid then
       return mid

else if a[mid] < mid then
        recursive call (a,mid+1,last)

else 
         recursive call (a,first,mid-1)

回答by Khaled.K

Java:

爪哇：

public static boolean check (int [] array, int i)
{
    if (i < 0 || i >= array.length)
        return false;

    return (array[i] == i);
}

C++:

C++：

bool check (int array[], int array_size, int i)
{
    if (i < 0 || i >= array_size)
        return false;

    return (array[i] == i);
}

回答by Vasu

Its not require to think in terms of any array Yas suggested in answerby @codaddict.

它不需要考虑@codacci回答中Y建议的任何数组。

Use binary search and check the middle element of given array, if it is lower than its index, than we do not need to check for any lower index because the array is sorted and so if we move to the left, subtracting m indexes and (at least) m value, all subsequent elements will also be too small. E.g. if arr[5] = 4then arr[4] <= (4 - 1)and arr[3] <= (4 - 2)and so on. Similar logic can be apply if middle element is greater than its index.

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

Here is simple Javaimplementation:

下面是简单的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
}

Note that the above solution would work only if all elements are distinct.

请注意，仅当所有元素都不同时，上述解决方案才有效。

回答by Henley Chiu

This is a solution I came up with, and it works if there are duplicates (I mistakenly overlooked that caveat of there being no duplicates).

这是我想出的一个解决方案，如果有重复，它就可以工作（我错误地忽略了没有重复的警告）。

//invariant: startIndex <= i <= endIndex

int modifiedBsearch(int startIndex, int endIndex)
{
   int sameValueIndex = -1;
   int middleIndex = (startIndex + endIndex) /2;
   int middleValue = array[middleIndex];
   int endValue = array[endIndex];
   int startValue = array[startIndex];

   if(middleIndex == middleValue)
      return middleValue;
   else {
      if(middleValue <= endIndex)
         sameValueIndex = modifiedBsearch(middleIndex + 1, endIndex)

      if(sameValueIndex == -1 && startValue <= middleIndex)
         sameValueIndex = modifiedBsearch(startIndex, middleIndex -1);
   }

   return sameValueIndex;

}

I would guess this takes O(log n) time, but this isn't clear in first glance???

我猜这需要 O(log n) 时间，但这乍一看不清楚？？？

If you're unlucky, it'll take O(n log n) time (the height of the stack tree will be log n, and it will be a full tree, with n nodes in the last level, n/2 in next to last, etc.).

如果你不走运，它将花费 O(n log n) 时间（堆栈树的高度将为 log n，它将是一棵完整的树，在最后一层有 n 个节点，在下一层有 n/2持续等）。

So, on average it will be between O(log n) and O(n log n).

因此，平均而言，它将介于 O(log n) 和 O(n log n) 之间。