c 程序使用 logn 时间复杂度查找升序数组中的重复元素

Question

这个问题已经有答案了:

Binary Search O(log n) algorithm to find duplicate in sequential list? (3 个回答)

已关闭 6 年前。

数组按升序排列，需要找出重复的数字需要一个时间复杂度为logn的程序

        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

如果您假设数字必须从 0 开始并以 1 递增，您可以将中间值与索引进行比较。如果中间相同，则较高，如果中间不同，则较低。

这将为您提供二分搜索时间 O(log2 N)。唯一的区别是您正在与索引进行比较，而不是与固定值进行比较。示例:int n[] = {0,1, 2, 3, 4, 5, 5, 6};注:数字以0开头如果数字以 1 开头，则相应地更改索引

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;
}