CODEWITHSUNDEEP
arraysalgorithmdivide-and-conquer
Ilan Aizelman WS
Ilan Aizelman WS

Reputation: 1632

Given sorted integer array, write an algo based on divide and conquer for A[i]=i

Given: sorted integer array, integers are all different - no duplicates.

Problem: Write an algorithm (as good as possible in runtime) based on divide and conquer for checking if there is an index i that A[i]=i exists in the array.

Well I thought about Binary Search which is O(logn) run time complexity. Is there something faster than that?

Upvotes: 0

Views: 169

Answers (3)

trincot
trincot

Reputation: 350310

The requirement that the input is sorted in itself is not enough. The additional requirement that there are no two equal values in the input array is a necessary condition to be able to use a binary search.

If that would not be a condition, you could not use a binary search, as can be seen in the following example (assuming 0 is the first index):

    i:   0 1 2 3 4 5 6
        --------------
  A[i]: -1 0 x 4 y 6 7
               ^

With a binary search you'd take the middle element and decide at which side of it there could be an i with A[i]=i. The problem is that in the above example the solution could be at either side of the centre: if x=2, then the solution is at the left, and when y=4, the solution is at the right. So divide and conquer will not work. Only when it is assured that the input has no duplicate values, a divide and conquer algorithm can work.

On top of that you can immediately exclude input arrays where the first value is greater than 0, because then there is no way to achieve A[i]=i without having duplicate values. Similarly, an input array where the last value is less than the last index, does not have an i with A[i]=i.

This consideration will also work during the divide and conquer. Take this example:

    i:   0 1 2 3 4 5 6 7 8
        -------------------
  A[i]: -4 0 1 2 5 6 7 8 10

At first both values at the ends are verified: they don't exclude a solution, so the middle value at index 4 is taken. Since its value (5) is greater than the index (4), the range from index 4 to 8 can be ignored. So in the next iteration of the algorithm the range between index 0 and 3 (included) are considered.

But the value at the rightmost index (3) is less than 3 (it is 2). By the above mentioned rule, this means there cannot be a solution, and so the algorithm can stop right there: making more divisions would be futile.

So here is a JavaScript implementation for this:

function hasSelfReference(arr) {
    let last = arr.length - 1;
    if (last < 0 || arr[0] > 0 || arr[last] < last) return false;

    let first = 0;
    while (first < last) {
        let mid = (first + last) >> 1;
        if (arr[mid] < mid) {
            first = mid + 1;
            if (arr[first] > first) return false;
        } else if (arr[mid] > mid) {
            last = mid - 1;
            if (arr[last] < last) return false;
        } else 
            return true;
    }
    return arr[first] === first; // arr[first] may be undefined: not a problem in JS
}

console.log(hasSelfReference([3, 4, 5, 6])); // false
console.log(hasSelfReference([-4, -2, 1, 2, 7])); // false
console.log(hasSelfReference([-4, -2, 1, 3, 7])); // true
console.log(hasSelfReference([])); // false
console.log(hasSelfReference([-4, 0, 1, 2, 5, 6, 7, 8, 10])); // false

As with the usual divide and conquer algorithms, this has a O(logn) (worst-case) time complexity.

When the array has a matching index, then the number of iterations is logn, but when there is no match, and the array is large, there will often be an early exit out of the loop.

Upvotes: 2

Aashi
Aashi

Reputation: 66

I think it will be best to use binary search as

1) You are given sorted integers

2) You need a divide and conquer algorithm

3) Running time of binary search is O(logn) which is better than linear search

Upvotes: 1

Henry
Henry

Reputation: 43738

Let's look at an example: assume A[i]=i-1 for all indices exept k, where A[k]=k. Just sampling the array at one place does not tell you anything about the position of k (unless you happen to hit k by pure luck).

Therefore, I don't think that you can get a worst case runtime better than O(n).

Upvotes: 2

Related Questions