I am trying to implement custom binary search. I am clear on how to pass arguments and what to compare to get in which kind of sorted order but I want to avoid the iteration as I want to get lower bound.
I am trying to get the highest rating "os" with the desired "query" using binary search. Am I implementing the binary search wrong here?
import java.util.*;
import java.io.*;
public class CustomBinarySearch {
static class OsDetails{
String os;
int memory, version, price, rating;
OsDetails(String s1, int a1, int b1, int c1, int d1){
os = s1;
memory = a1;
version = b1;
price = c1;
rating = d1;
}
public String toString() {
return os+"-"+String.valueOf(memory)+"-"+String.valueOf(version)+"-"+String.valueOf(price)+"-"+String.valueOf(rating);
}
} // custom class for os details
static class Comp implements Comparator<OsDetails>{
public int compare(OsDetails p1, OsDetails p2) {
if(p1.os.equals(p2.os) && p1.memory==p2.memory && p1.version==p2.version) {
return 0;
}
else {
return -1;
}
}
} // binary search comparator
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<OsDetails> list = new ArrayList<OsDetails>();
StringTokenizer st;
for(int i = 0;i<n;i++) {
st = new StringTokenizer(br.readLine());
list.add(new OsDetails(st.nextToken(), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
Collections.sort(list, new Comparator<OsDetails>() {
@Override
public int compare(OsDetails p1, OsDetails p2) {
if(p1.os.equals(p2.os)) {
if(p1.memory==p2.memory) {
if(p1.version==p2.version) {
if(p1.rating==p2.rating) {
return p1.price-p2.price;
}
else {
return p2.rating-p1.rating;
}
}
else {
return p1.version-p2.version;
}
}
else {
return p1.memory-p2.memory;
}
}
else {
return p1.os.compareTo(p2.os);
}
}
}); // sorting on the based on 1. String 2. memory(2 or 4) 3. version (32 or 64 bit) 4. rating(higher to lower) 5. price(low to high)
System.out.println(list);
int q = Integer.parseInt(br.readLine());
for(int i = 0;i<q;i++) {
st = new StringTokenizer(br.readLine());
OsDetails pfind = new OsDetails(st.nextToken(), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
int j = Collections.binarySearch(list, pfind, new Comp());
int k=j;
if(j<0) {
System.out.println(-1);
continue;
}
OsDetails plist = list.get(j);
while(k>=0) {
plist = list.get(k);
if(pfind.os.equals(plist.os) && pfind.memory==plist.memory && pfind.version==plist.version && pfind.price>=plist.price) {
k--;
}
else {
break;
}
} // I want to avoid this iteration please suggest some way out of this
plist = list.get(k+1);
if(pfind.os.equals(plist.os) && pfind.memory==plist.memory && pfind.version==plist.version && pfind.price>=plist.price)
System.out.println(plist.rating);
else
System.out.println(-1);
}
}
}
/*
7
android 2 32 76 84
ios 2 32 78 100
windows 2 32 56 79
windows 2 32 110 100
windows 2 64 73 38
ios 4 64 100 500
ios 4 64 107 50
3
ios 4 64 300
windows 2 32 500
ios 2 32 70
*/
There are multiple problems with your code.
First of all, your first comparator only returns 0 or -1. But the comparator interface says: -1, 0, or 1. So your implementation there must be wrong somehow.
Then: one of the reasons why your code is so hard to read: naming variables a, b, c, d, to then write manual code to "deal" with those 4 values is "wrong" conceptually.
Those 4 values should go into a list or array. And then your Pair class could be named FixedLengthArray or something alike. And then you could avoid such endless cascades of if/else ... by iterating these arrays when needing to make comparisons.
Your real problem isn't iteration, it is the way how you represent your data here.