0

我尝试使用Arrays.binarySearch来查找数组中整数对的数量。在以下数组中，蛮力算法将找到 4 对。但是二进制搜索版本给出了 3，这是错误的答案。

蛮力：

public static int brutePairCount(int[] a){
        int paircount = 0;
        int N = a.length;
        for(int i=0;i<N;i++){
            for(int j=i+1;j<N;j++){
                if(a[i]==a[j] ){
                    paircount++;
                }
            }
        }
        return paircount;
    }

public static void main(String[] args) {
    int[] nums = new int[]{12, 12, 23, 23, 45, 67, 75, 75, 85, 92, 111, 113, 113, 134, 142, 156};
    int cnt1 = brutePairCount(nums);
    System.out.println("pairs="+cnt1);
}

二进制搜索：

public static int bsPairCount(int[] a){
        Arrays.sort(a);
        int paircount = 0;
        int N = a.length;
        for(int i=0;i<N;i++){
            int key = a[i];
            int idx = Arrays.binarySearch(a, key);
            if(idx > i){
                paircount++;
            }
        }
        return paircount;
    }

public static void main(String[] args) {
    int[] nums = new int[]{12, 12, 23, 23, 45, 67, 75, 75, 85, 92, 111, 113, 113, 134, 142, 156};
    int cnt1 = bsPairCount(nums);
    System.out.println("pairs="+cnt1);
}

我发现逻辑

if(idx > i){
   paircount++;
}

是错误的来源。我的调试器显示，在i=11, key =113，binarysearch(key)返回11本身，因此计数不会增加。

来自的javadocs Arrays.binarySearch：

如果范围包含多个等于指定对象的元素，则无法保证会找到哪一个。

我想我找到了问题，但我该如何解决呢？我的大脑有点糊涂（睡眠不足：（）..有人能解释一下吗？

4

0 回答 0