二进制搜索O（log n）的算法找出重复的顺序表？ [英] Binary Search O(log n) algorithm to find duplicate in sequential list?

问题描述

有谁知道快于线性算法查找重复的号码顺序表？我用Java开发的，但现在任何语言或psuedo- code是好的。

Does anyone know a faster-than-linear algorithm for finding a duplicate in a sequential list of numbers? I'm working in Java now but any language or psuedo-code is fine.

例如，鉴于此INT []输入：

For example, given this int[] input:

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

输出将是无论是指数或值7。

Output would be either index or value '7'.

我知道 O（N）线性时间明显遍历，但是我想看看这是可以通过二进制搜索在 O（log n）的的时间。

I know the obvious traversal at O(n) linear time, but I'm trying to see if this is possible via binary search at O(log n) time.

推荐答案

如果您认为该数字必须从0开始，用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.

这会给你二进制搜索时间为O（LOG2 N）。唯一的区别是，你是比较与索引，而不是一个固定的值。

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.

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

这篇关于二进制搜索O（log n）的算法找出重复的顺序表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！