为什么内置Java二进制搜索只返回负指数？

Question

给定带有参数（a，b）的State对象，我想使用java的binarysearch方法能够快速定位数组中的State。应该首先通过增加“a”值来命令状态，然后如果是平局则增加“b”值。此外，所有国家都是简单的。

目标是找到有多对状态具有相反的参数值，或满足：

State 1 = (a,b)
State 2 = (b,a)

下面的测试数据应输出1，将状态1和3组合在一起。但是，我的输出为0，调试显示我的所有bsearches都返回负值。显然其中两个应该是积极的

主要方法：

/*
Test data (each state on a new line):
320 141
78 517
141 320
63 470
40 312
381 141
*/

    State[] states = new State[n];

    //Read in input (not shown)
    Arrays.sort(states);

    int ret = 0;

    for (int i = 0; i < n; i++) {
        State other = new State(states[i].b,states[i].a);
             //search for state with opposite parameters

        int index = Arrays.binarySearch(states, other);

        System.out.println(index); //debugging purposes

        if (index > -1)
            ret++;
    }


    System.out.println(ret/2); //avoid doublecounting (a/b and b/a)

州级：

static class State implements Comparable<State> {
    int a,b; //State parameters

    public State(int a, int b) {
        this.a=a;
        this.b=b;
    }
    public int compareTo(State other) {
        if (this.a > other.a) //first sort by "a" values
            return 1;
        else if (this.a == other.a && this.b > other.b) //"a" tie, now sort by "b"
            return 1;
        else 
            return -1; 
    }
}

调试产生以下索引：

-5
-7
-7
-6
-5
-5

谁能找到问题呢？

我很确定它不是重复的。那张海报没有事先对他的阵列进行排序，并且在他的bsearch键中包含了空格。

Answer 1

你的compareTo方法被打破了。合同说this.compareTo(this)应该返回0。您的实现永远不会返回0。

错误的compare或compareTo方法可能导致数组被错误地排序，和/或导致二进制搜索失败。有了这个特定的错误，可能就是后者。二进制搜索只能在compareTo方法返回零时“找到”一个元素。