二进制搜索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

public class DuplicateNumber {

    public int findDuplicateNumber(List<Integer> numbers){

        int highestNumber = numbers.size() - 1;
        int total = getSum(numbers);
        int duplicate = total - (highestNumber*(highestNumber+1)/2);
        return duplicate;
    }

    public int getSum(List<Integer> numbers){

        int sum = 0;
        for(int num:numbers){
            sum += num;
        }
        return sum;
    }

    public static void main(String a[]){
        List<Integer> numbers = new ArrayList<Integer>();
        for(int i=1;i<30;i++){
            numbers.add(i);
        }
        //add duplicate number into the list
        numbers.add(22);
        DuplicateNumber dn = new DuplicateNumber();
        System.out.println("Duplicate Number: "+dn.findDuplicateNumber(numbers));
    }
}

Answer 2

请注意，二进制搜索适用于排序列表。因此，如果您有一个具有重复项的排序列表，则二进制搜索只有在您的重复项相邻时才有用。相邻的重要性是为了您可以测试键在找到的键的上一个和下一个位置的存在。任何其他尝试在未排序列表上使用二进制搜索的方法都会给出不正确的结果。

这里有一些代码来说明我的意思

import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        int[] list = {1, 2, 3, 4, 5, 6, 7, 7, 8, 9 };
        int key = 7;
        int result = Arrays.binarySearch(list, key);
        System.out.println(result);
        if( list[result+1] == key  || list[result-1] == key )
                System.out.println("yes we have a duplicate.");
    }
}

如果中的比较是O（1），我们仍然使用二分搜索的O（logn）。

Answer 3

如果您假设数字必须从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;
}