c program to find the duplicate element in an ascending array using logn time complexity

Question

Array is in ascending order need to find the duplicated number Need a program with logn time complexity

        int n[] = {1, 2, 3, 4, 5, 5, 6};


        int size = sizeof[n];
        int mid;
            mid = size/ 2 ;
            if (a[mid] == a[mid + 1])
                        printf("%d",a[mid]);
                        return a[mid];

            else if (a[mid] != a[mid + 1])
                        for(int i=0;i<mid;i++){
                                        if(a[i]==a[mid+1])
                                           return a[i];
           }
           else
                        for(int i=mid ;mid<size;i++){
                                        if(a[mid]==a[mid+1])
                                           return a[mid];
           }

Answer 1

If you assume the numbers must start at 0 and be increasing by 1 you can compare the middle to the index. If the middle is the same go higher, if the middle is not, go lower.

This will give you binary search time O(log2 N). The only difference is that you are comparing with the index, rather than a fixed value. example : int n[] = {0,1, 2, 3, 4, 5, 5, 6}; note: number start with 0 if number is started with 1 than change index accordingly

int findDuplicate(int array[],int n) {
int low = 0;
int high = n - 1;

while (low <= high) {
    int mid = (low + high)/2;
    int midVal = array[mid];

    if (midVal == mid)
        low = mid + 1;
    else
        high = mid - 1;
}
return high;
}