java - 对字符串的特定部分进行二分查找

Question

这是一个字符串9*8*0.01548位于 ArrayList<String> 。我需要基于 Double 进行二分搜索值即 0.01548找到搜索值的紧密匹配。 ArrayList包含大约 100 万条记录。 Split就优化而言似乎不是一个好的选择。 我尝试了以下代码，但它不起作用，因为列表中间值是根据列表大小计算的 3 。二分搜索本身很好，我只是为了问题的清晰而添加，如果Double值在 arrayListvalues 中然后二分搜索工作正常

1. 有哪些可能的替代方案？
2. 如何使其发挥作用？

下面是:

public static <T> int binarySearch(List<T> list, T key, Comparator<T> compare) {
int low, high, med, comp;
        T temp;
        high = list.size();
        low = 0;
        med = (high + low) / 2;

        while (high != low + 1) {
            temp = list.get(med);
            comp = compare.compare(temp, key);

            if (comp == 0) {
                return med;
            } else if (comp < 0) {
                low = med;
            } else {
                high = med;
            }

            med = (high + low) / 2;
        }

        return med;
    }

比较器

public static class doubleComparator implements Comparator<String> {

 @Override
        public int compare(String s1, String s2) {
            String[] d1 = s1.split("*"); //this
            String[] d2 = s2.split("*"); //that
            if (Double.parseDouble(d1[2]) < Double.parseDouble(d2[2])) {
                return -1;
            } else if (Double.parseDouble(d2 [2]) > Double.parseDouble(d2[2])) {
                return 1;
            } else {
                return 0;
            }
        }
    }

主要

 public static void main(String[] args) {
 ArrayList<String> strArray= new ArrayList<String>();
        strArray.add("1*2*0.1");
        strArray.add("3*4*0.5");
        strArray.add("5*6*0.6");
        strArray.add("7*8*0.7");
        strArray.add("9*10*0.8");
        strArray.add("11*12*0.9");
        int key = binarySearch(strArray, "45*60*0.3", new doubleComparator());
        System.out.println("Search for "45*60*0.3:"\tKey:" + key + "\tValue:" + strArray.get(key));
}

Answer 1

考虑改变这里的核心元素:为什么要使用带有字符串的ArrayList；如果您有超过一百万个条目；您需要快速获取 double 吗？

为什么不进行预计算:当你获取初始记录时；将它们分成两个列表；一个包含完整字符串...另一个仅包含(已计算和转换) double 值？哎呀，如果对象的数量没有改变；您甚至可以将它们放入一个数组中(对于一百万个条目， array[double] 的成本比 ArrayList 的成本要小得多)。

含义:有时尝试围绕表现不佳的数据构建“高效”算法是浪费时间。相反，更改数据的表示形式，以便您可以有效地处理它......

当然，这取决于......数据更改......数据需要(重新)计算......这些搜索发生的频率。只是说您不应该专注于“正确搜索”。