java - 二分搜索 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;
}

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) 中的比较if仍然是二进制搜索的 O(logn)。

Answer 3

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