0

我正在尝试使用二进制搜索来查找包含子字符串的字符串。

ArrayList<String> ch = new ArrayList<String>();
    ch.add("qwerty");
    ch.add("asdfghjkl");
    ch.add("c");
    ch.add("d");
    ch.add("e");
    Comparator<String> comparator = new Comparator<String>() {
        public int compare(String node1, String node2) {
            if (node1.contains(node2)) {
                return 0;
            }
            return node1.indexOf(node2);
        }
    };


    int pos2 = Collections.binarySearch(ch, "sdf", comparator);

是否可以使用二进制搜索而不是使用循环。这给了我一个不正确的索引。

我试图避免使用 string.substring(x,y) ，其中 x 和 y 是固定值。

4

4 回答 4

2

Collections.binarySearch方法用于搜索完全匹配，而不是基于某些子字符串或某些方法的匹配。此外，为了binarySearch工作，你应该有一个排序数组，基于Comparator你传递给binarySearch方法的那个（虽然，这在这里无关紧要，因为它也不起作用）。

是否可以使用二进制搜索而不是使用循环。

我认为不使用循环就不可能做到这一点。如果您真的担心性能，您可以编写自己的二进制搜索实现，它检查contains()而不是相等。

于 2013-10-16T17:55:28.953 回答
1

问题：您只能对已排序的集合进行二分搜索。
解决方案：Comparator在调用之前使用您的集合对您的集合进行排序binarySearch()；

问题：您的比较器必须满足接口要求。例如，您的排序函数必须是传递的。
解决方案：实现这一目标的唯一可能方法是使用Comparator每个字符串。

public static void main(String[] args) {
    ArrayList<String> ch = new ArrayList<String>();
    ch.add("qwerty");
    ch.add("asdfghjkl");
    ch.add("c");
    ch.add("d");
    ch.add("e");
    final String fixedString = "sdf";
    Comparator<String> comparator = new Comparator<String>() {
        public int compare(String node1, String node2) {
            boolean node1Contains = node1.contains(fixedString);
            boolean node2Contains = node2.contains(fixedString);
            if (node1Contains && !node2Contains) {
                return 1;
            } else if (!node1Contains && node2Contains ) {
                return -1;
            } else {
                return 0;
            }
        }
    };

    Collections.sort(ch, comparator);
    int pos2 = Collections.binarySearch(ch, fixedString, comparator);
    System.out.println("Sorted collection: "+ch);
    System.out.println("Index found: "+pos2);
}

输出：

Sorted collection: [qwerty, c, d, e, asdfghjkl]
Index found: 4

底线：

不考虑字符串的大小和调用contains()这么多次的成本：

  • 排序将花费O(n log(n))（n字符串的数量在哪里）并且搜索将花费O(log(n))，因此，总体而言，O(n log(n))。
  • 循环将采取O(n).

因此，除非您想获得诸如“在最少索引中具有搜索字符串的字符串（更接近其开头）”，否则最好循环遍历。

于 2013-10-16T18:01:38.743 回答
0

在搜索 API 中提到的项目之前，必须对列表进行排序。

http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#binarySearch(java.util.List , T)

此外，比较函数应该返回 -1,0,1 作为响应，看起来它没有做它应该做的事情。

于 2013-10-16T17:58:28.373 回答
0

比较器实际上是用来比较两个对象以确定它们相对于彼此的相对顺序。如果 node1 在 node2 之前，compare 方法应该返回 -1，如果在 node2 之后，则返回 1，如果它们是相同的 String，则返回零。

如果一个是另一个的子字符串，您的 compare 方法返回 0，否则返回 -1，因此 binarySearch 将对此感到非常困惑。此外，二进制搜索假定数组已排序，并且仅当您在数组中查找确切的字符串而不是包含子字符串的字符串时才有效。您只需要遍历数组并查看每个数组是否包含您要查找的子字符串。

于 2013-10-16T18:01:44.427 回答