Divide and Conquer Algorithms- Binary search variant

0
votes

This is a practice question for the understanding of Divide and conquer algorithms.

You are given an array of N sorted integers. All the elements are distinct except one element is repeated twice. Design an O (log N) algorithm to find that element.

I get that array needs to be divided and see if an equal counterpart is found in the next index, some variant of binary search, I believe. But I can't find any solution or guidance regarding that.

2
algorithmbinary-searchdivide-and-conquer
Are these consecutive integers? - Mark Ransom
No. This is the exact text of the question and it doesn't mention consecutive integers. - someone
I don't think there is a logN solution when it is not consecutive numbers. - Idos
To achieve log(N) you need some criterion to discard half of the array at each iteration. With random (though sorted) integers there is no such criterion, and you need to ultimately check all the elements, which makes it worst case O(N). Possibly the author of the question was thinking of an array of 1..N-1 elements (i.e., consecutive). - LSerni
This seems too similar to the consecutive numbers question, probably that was left out on mistake, since if not - then the consecutive sorted array question has redundant information, and it doesn't :) - Ron.B.I

2 Answers

3
votes

You can not do it in O(log n) time because at any step even if u divide the array in 2 parts, u can not decide which part to consider for further processing and which should be left. On the other hand if the consecutive numbers are all present in the array then by looking at the index and the value in the index we can decide if the duplicate number is in left side or right side of the array.

0
votes

D&C should look something like this

int Twice (int a[],int i, int j) {
    if (i >= j)
       return -1;
    int k = (i+j)/2;
    if (a[k] == a[k+1]) 
       return k;
    if (a[k] == a[k-1])
       return k-1;
    int m = Twice(a,i,k-1);
    int n = Twice(a,k+1,j);
    return m != -1 ? m : n;
}


int Twice (int a[], int n) {
    return Twice(a,0,n);
}

But it has complexity O(n). As it is said above, it is not possible to find O(lg n) algorithm for this problem.