Divide and Conquer Algorithms- Binary search variant

Question

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.

No. This is the exact text of the question and it doesn't mention consecutive integers. — someone
– someone, Commented Dec 6, 2015 at 17:19
I don't think there is a logN solution when it is not consecutive numbers. — Idos
– Idos, Commented Dec 6, 2015 at 17:22
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
– LSerni, Commented Dec 6, 2015 at 17:23
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
– Ron.B.I, Commented Dec 6, 2015 at 17:24

Ashu · Accepted Answer · 2015-12-06 17:27:01Z

3

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.

answered Dec 6, 2015 at 17:27

Ashu

1855 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

noname · Accepted Answer · 2019-10-10 06:20:10Z

0

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.

answered Oct 10, 2019 at 6:20

noname

663 bronze badges

Collectives™ on Stack Overflow

Divide and Conquer Algorithms- Binary search variant

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related