如何使用比较器执行二进制搜索？

Question

我正在尝试使用不区分大小写的比较器执行二进制搜索，但无论我尝试什么，我都会不断出错...

试用 1：

Arrays.binarySearch(arr, "text", String::compareToIgnoreCase);

来源：

这给出了一个错误：

Method references are not supported at language level '7'

假设我想使用 Java 7，我尝试了这些额外的方法：

试用 2:

Comparator<String> caseInsensitiveComparator = new Comparator<String>() {
        @Override
        public int compare(String s, String t1) {
            return s.compareToIgnoreCase(t1);
        }
    };

Arrays.binarySearch(arr, "text", caseInsensitiveComparator);

来源：

错误：

Required type: Comparator<? super Object>
Provided: Comparator

请注意，此方法适用于对列表进行排序（即此比较器适用于Collections.sort()）

试用 3：

Arrays.binarySearch(arr, "text", String.CASE_INSENSITIVE_ORDER);

来源：

错误：

Required type: Comparator<? super Object>
Provided: Comparator

注意这个方法也适用于Collections.sort()

试验4：

构建一个实现 Comparator<String>:

的 class

public class CaseInsensitiveComparatorClass implements Comparator<String> {

    @Override
    public int compare(String s, String t1) {
        return s.compareToIgnoreCase(t1);
    }
}

Arrays.binarySearch(arr, "text", new CaseInsensitiveComparatorClass ());

来源：

错误：

Required type: Comparator<? super java.lang.Object>
Provided: CaseInsensitiveComparatorClass

注意这个方法也适用于Collections.sort()

你能给我提供一种有效的方法，或者指出我做错了什么吗？

编辑：

这是arr的声明：

private List<String> lst;

所以它实际上是一个列表，我在方法调用时将其转换为数组：

Arrays.binarySearch(lst.toArray(),...

Answer 1

试试这个代码：

    String[] arr = {"a","b","c"};

    int i = Arrays.binarySearch(arr, "B", new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o1.compareToIgnoreCase(o2);
        }
    });

    System.out.println(i);

Answer 2

关于您的第一个示例，您使用了 Java 8 (String::compareToIgnoreCase) 中的方法参考功能，但是您 compile/execute 代码使用 Java 7. 更改 Java 至少到 Java 8. 还请记住，在使用 Arrays.binarySearch 之前，应对您的数组进行排序。

收集可以使用以下方法：Collections.binarySearch()

为了将列表转换为具有通用参数的数组，请使用以下内容：

lst.toArray(new String[0]);

Answer 3

您实际上有一个列表而不是数组：List<String>。使用 Collections.binarySearch 而不是将列表转换为数组后跟 Arrays.binarySearch.

List<String> lst = Arrays.asList("a", "text", "z"); // just an example list
int index = Collections.binarySearch(lst, "text", String.CASE_INSENSITIVE_ORDER);

如果出于某些愚蠢的原因必须使用 Arrays.binarySearch，您可以将具体列表类型作为参数传递给 List.toArray。这将使方法 return 成为字符串数组而不是对象数组：

Arrays.binarySearch(lst.toArray(new String[0]), String.CASE_INSENSITIVE_ORDER)

Answer 4

注意数组要按照Arrays.binarySearchJavadoc:

排序

Searches the specified array for the specified object using the binary search algorithm. The array must be sorted into ascending order according to the specified comparator (as by the sort(T[], Comparator) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements equal to the specified object, there is no guarantee which one will be found.

String本身实现了Comparable接口，所以不需要再实现新的

以下是可视化如何使用 Arrays.binarySearch 的简短代码片段。

public class BinarySearch {
    public static void main(String[] args) {
        final String[] arr = {"one", "two", "three", "four", "text"};

        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println(Arrays.binarySearch(arr, "text", String.CASE_INSENSITIVE_ORDER));
    }
}

如何使用比较器执行二进制搜索？

How to perform a binarySearch with a comparator?

java

comparator