为 4 个参数实现了自定义二进制搜索，但如何避免迭代获得下限？

Question

我正在尝试实现自定义二进制搜索。我很清楚如何传递参数以及比较什么以获得哪种排序顺序，但我想避免迭代，因为我想获得下限。

我正在尝试使用二进制搜索获得最高评分 "os" 和所需的 "query"。我在这里实施二分查找错误吗？

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

您的代码存在多个问题。

首先，你的第一个比较器只有returns0或-1。但是比较器接口说：-1, 0, or 1. 所以你在那里的实现一定不知何故是错误的。

然后：你的代码这么难读的原因之一：命名变量a，b，c，d，然后写manual代码到"deal" 这 4 个值在概念上是 "wrong"。

这 4 个值应放入列表或数组。然后你的 Pair class 可以命名为 FixedLengthArray 或类似的名字。然后你可以通过在需要进行比较时迭代这些数组来避免 if/else 这样无休止的级联。

您真正的问题不是迭代，而是您在此处表示数据的方式。

为 4 个参数实现了自定义二进制搜索，但如何避免迭代获得下限？

Implemented Custom Binary search for 4 arguments but how to avoid the iteration to get lowerbound?

java

binary-search

comparator