二进制搜索O(log n)算法在顺序列表中查找重复？

Question

有没有人知道在序列号列表中找到重复的比线性更快的算法？我现在在Java工作,但任何语言或伪代码都没问题.

例如,给定此int []输入:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 7 | 8 | 9

输出可以是指数或值'7'.

我知道O(n)线性时间的明显遍历,但我正试图通过二进制搜索来确定这是否可行O(log n).

Answer 1

如果假设数字必须从0开始并且增加1,则可以将中间值与索引进行比较.如果中间是相同的更高,如果中间不是,则降低.

这将为您提供二进制搜索时间O(log2 N).唯一的区别是您要与索引进行比较,而不是固定值.

public static void main(String... args) {
    int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9};
    int duplicate = findDuplicate(array);
    System.out.println(duplicate);
}

private static int findDuplicate(int[] array) {
    int low = 0;
    int high = array.length - 1;

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

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