Given State objects with parameters (a,b), I want to use java's binarysearch method to be able to quickly locate a State in an array. The States should be ordered first by increasing "a" values, and then "b" values if theres a tie. Also, all the States are distinct for simplicity.
The goal is to find how many pairs of states have opposite parameter values, or satisfy:
State 1 = (a,b)
State 2 = (b,a)
The test data below should output 1, pairing States 1 and 3 together. However, mine outputted 0, and debugging showed that all my bsearches returned negative values. Obviously two of them should have been positive
Main method:
/*
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)
State class:
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;
}
}
Debugging yields the following indices:
-5
-7
-7
-6
-5
-5
Can anyone find the problem?
I'm pretty sure it isn't a duplicate. The poster there didn't sort his array beforehand, and was including whitespace in his bsearch key.
