CODEWITHSUNDEEP
javaarraysalgorithm
Yadasko
Yadasko

Reputation: 33

Check if a value in Array correspond to it place

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 !

Upvotes: 3

Views: 83

Answers (6)

MrSmith42
MrSmith42

Reputation: 10151

simply use a binary search for the 0 and use for compare the value in the array minus index of the array. O(log n)

Upvotes: 0

AhmadWabbi
AhmadWabbi

Reputation: 2197

Here is an algorithm (based on binary search) to find all matching indices that has a best-case complexity of O(log(n)) and a worst case complexity of O(n):

1- Check the element at position m = array.length / 2

2- if the value array[m] is strictly smaller than m, you can forget about the left half of the array (from index 0 to index m-1), and apply recursively to the right half.

3- if array[m]==m, add one to the counter and apply recursively to both halves

4- if array[m]>m, forget about the right half of the array and apply recursively to the left half.

Using threads can accelerate things here. I suppose that there is no repetitions in the array.

Upvotes: 2

Thomas
Thomas

Reputation: 88707

Using binary search (or a similar algorithm) you could get better than O(n). Since the array is sorted, we can make the following assumptions:

  • if the value at index x is smaller than x-1 (a[x] <= x), you know that all previous values also must be smaller than their index (because no duplicates are allowed)
  • if a[x] > x + 1 all following values must be greater than their index (again no duplicates allowed).

Using that you can use a binary approach and pick the center value, check for its index and discard the left/right part if it matches one of the conditions above. Of course you stop when a[x] = x + 1.

Upvotes: 0

Priyatam Roy
Priyatam Roy

Reputation: 83

You can skip iterating if there is no such element by adding a special condition

if(a[0]>1 && a[a.length-1]>a.length){
    //then don't iterate through the array and return false
    return false;
} else {
    //make a loop here
}

Upvotes: 0

kfx
kfx

Reputation: 8537

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.

Upvotes: 1

Serge Ballesta
Serge Ballesta

Reputation: 148965

If you want the find the first number in the array that is at its own place, you just have to iterate the array:

static int find_in_place(int[] a) {
    for (int i=0; i<a.length; i++) {
        if (a[i] == i+1) {
            return a[i];
        }
    }
    return 0;
}

It has a complexity of O(n), and an average cost of n/2

Upvotes: 0

Related Questions