java - 用字符串前缀实现二进制搜索？

Question

如何实现二进制搜索以在通用数组(在本例中为字符串 [])中查找具有特定前缀的字符串。我尝试了 compareTo 但这无济于事，因为我必须使用字符串前缀。例如字符串前缀“Bi”bill, bilards ...等等。

实现以下方法以返回按字母顺序排序的数组中以给定前缀开头的所有字符串。例如，给定前缀“bi”，返回的字符串是“Bill Clinton”、“Bill Gates”和“Bill Joy”。请注意，所有字符串比较都应该不区分大小写。返回列表中的字符串必须按照它们在数组中出现的顺序排列。您的实现必须基于二进制搜索，并且必须在最坏情况下运行 O(log n+k) 时间，其中 n 是数组的长度，k 是匹配字符串的数量。假设该数组没有重复条目。如果没有匹配项，您可以返回 null 或一个空数组列表。

您可以使用以下字符串方法(以及您可能记得的任何其他方法): boolean startsWith(String s) int compareTo(字符串 s) int compareToIgnoreCase(String s) 字符串 toLowerCase(String s) 字符串大写(String s) (对于ArrayList，只需要使用add方法在数组列表的末尾添加一项即可。) 您可以根据需要编写辅助方法(完整实现)。你不能调用任何你自己没有实现的方法

public static <T extends Comparable<T>> ArrayList prefixMatch(T[] list, String prefix) {

        ArrayList<T> result = new ArrayList<T>();
        int lo = 0;
        int hi = list.length - 1;

        while(lo <= hi) {

            int mid = (hi + lo) / 2;

            list[mid].startsWith(prefix) ? 0 : list[mid].compareTo((T) prefix));


        }   

        return null;
    }

Answer 1

您可以使用带有自定义比较器的默认二进制搜索作为基础，然后自行处理我们的范围。我认为正确的算法是:

1. 对给定数组执行二进制搜索。使用比较器仅检查前缀。
2. 结果你会得到以你的前缀开头的字符串索引
3. 向左走找到第一个匹配前缀的字符串，记住位置。
4. 向右走找到第一个匹配前缀的字符串，记住位置。
5. 从原始数组的范围开始到范围结束复制元素。这将是您想要的具有前缀匹配条件的所有元素的数组。

下面是java中的实现。它在快乐的情况下工作，但如果(我将这些检查留在外面以使代码看起来简单)会崩溃:

• 原数组中不存在给定前缀的字符串
• 存在长度小于前缀长度的字符串

此外，如果您需要二进制搜索实现，您可以检查 Arrays.binarySearch 的源代码

public class PrefixMatch {

    public static void main(String[] args) {

        final String[] prefixMathces = prefixMatch(new String[] { "Abc", "Abcd", "Qwerty", "Pre1", "Pre2", "Pre3", "Xyz", "Zzz" }, "pre");

        for (int i = 0; i < prefixMathces.length; i++)
            System.out.println(prefixMathces[i]);
    }

    public static String[] prefixMatch(final String[] array, final String prefix) {

        final Comparator<String> PREFIX_COMPARATOR = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.substring(0, prefix.length()).compareToIgnoreCase(o2);
            }
        };

        final int randomIndex = Arrays.binarySearch(array, prefix, PREFIX_COMPARATOR);

        int rangeStarts = randomIndex, rangeEnds = randomIndex;

        while (rangeStarts > -1 && array[rangeStarts].toLowerCase().startsWith(prefix.toLowerCase()))
            rangeStarts--;

        while (rangeEnds < array.length && array[rangeEnds].toLowerCase().startsWith(prefix.toLowerCase()))
            rangeEnds++;

        return Arrays.copyOfRange(array, rangeStarts + 1, rangeEnds);
    }
}