检查Array中的值是否与其对应(Check if a value in Array correspond to it place)

检查Array中的值是否与其对应(Check if a value in Array correspond to it place)

不久前我遇到了一个算法问题。

我需要查找存储在数组中的值是否位于“地点”。 一个例子将更容易理解。

我们取一个数组A = {-10，-3,3,5,7}。 该算法将返回3，因为数字3在A [2]（第3位）。 相反，如果我们采用数组B = {5,7,9,10}，算法将返回0或false或其他。

数组总是排序！

我无法找到具有良好复杂性的解决方案。 （单独观察每个值并不好！）也许有可能通过使用类似于合并排序的方法，通过减少一半并验证这两半来解决该问题？

有人可以帮我这个吗？ Java算法将是最好的，但伪代码也会帮助我很多！

I was confronted not so long ago to an algorithmic problem.

I needed to find if a value stored in an array was at it "place". An example will be easier to understand.

Let's take an Array A = {-10, -3, 3, 5, 7}. The algorithm would return 3, because the number 3 is at A[2] (3rd place). On the contrary, if we take an Array B = {5, 7, 9, 10}, the algorithm will return 0 or false or whatever.

The array is always sorted !

I wasn't able to find a solution with a good complexity. (Looking at each value individualy is not good !) Maybe it is possible to resolve that problem by using an approach similar to merge sorting, by cuting in half and verifying on those halves ?

Can somebody help me on this one ? Java algorithm would be the best, but pseudocode would also help me a lot !

最满意答案

由于不存在重复，您可以使用函数f(x): A[x] - x是单调的并应用二进制搜索来解决O(log n)最坏情况复杂度的问题。

您想要找到一个函数A[x] - x取值为零的点。 这段代码应该有效：

boolean binarySearch(int[] data, int size) { int low = 0; int high = size - 1; while(high >= low) { int middle = (low + high) / 2; if(data[middle] - 1 == middle) { return true; } if(data[middle] - 1 < middle) { low = middle + 1; } if(data[middle] - 1 > middle) { high = middle - 1; } } return false; }

注意Java中的数组是0索引的 - 这就是我从数组中减去-1的原因。

Since there can be no duplicates, you can use the fact that the function f(x): A[x] - x is monotonous and apply binary search to solve the problem in O(log n) worst-case complexity.

You want to find a point where that function A[x] - x takes value zero. This code should work:

boolean binarySearch(int[] data, int size) { int low = 0; int high = size - 1; while(high >= low) { int middle = (low + high) / 2; if(data[middle] - 1 == middle) { return true; } if(data[middle] - 1 < middle) { low = middle + 1; } if(data[middle] - 1 > middle) { high = middle - 1; } } return false; }

Watch out for the fact that arrays in Java are 0-indexed - that is the reason why I subtract -1 from the array.