Yadasko - 10 months ago 51

Java Question

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 !*

Answer

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.