Реализован пользовательский бинарный поиск по 4 аргументам, но как избежать итерации, чтобы получить нижний предел?

Question

Я пытаюсь реализовать пользовательский бинарный поиск.Мне ясно, как передавать аргументы и что сравнивать, чтобы получить в каком порядке сортировку, но я хочу избежать итерации, поскольку хочу получить нижнюю границу.

Я пытаюсь получить наивысший рейтинг "os" с желаемым "запросом", используя бинарный поискЯ неправильно реализую бинарный поиск?

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
*/

Answer 1

Есть несколько проблем с вашим кодом.

Прежде всего, ваш первый компаратор возвращает только 0 или -1.Но интерфейс компаратора говорит: -1, 0, или 1. Итак, ваша реализация там должна ошибаться.

Тогда: одна из причин, по которой ваш кодэто так трудно читать: именование переменных a, b, c, d, чтобы потом написать ручной код для «обработки» этих 4 значений, концептуально «неправильно».

Эти 4 значения должны войти в список или массив .И тогда ваш класс Pair может быть назван FixedLengthArray или как-то так.И тогда вы могли бы избежать таких бесконечных каскадов if / else ... путем итерации этих массивов при необходимости проводить сравнения.

Ваша настоящая проблема не в итерации, а в том, как вы представляете свои данные здесь.