利用 BinarySearch 做一个自动完成练习

Question

您好，我正在制作一个程序，该程序采用 "Terms" 数组，每个数组都有自己的权重（长值）和查询（字符串值）。它应该从 .txt 文件中获取许多术语并将它们初始化为私有 "Terms" 数组，然后它使用 arrays.sort 按字典顺序重新排列它们的查询。 Term[] allmatches(String prefix) 函数旨在利用二进制搜索在已经按字典顺序排序的 "Terms" 数组中查找第一个匹配开始和最后一个匹配结束的位置（我相信我的 prefixOrder 比较器和我的二进制搜索方法可以自己正常工作）。然后使用 "for" 循环，我尝试将所有这些特定术语复制到一个名为 "newterms." 的新数组中问题是我只有 return "null" 值。

public class Autocomplete {
private Term[] terms;

/**
 * Initializes the data structure from the given array of terms.
 * @param terms a collection of terms.
 */
public Autocomplete(Term[] terms) {
   if (terms == null) {
        throw new java.lang.NullPointerException(); }
   this.terms = terms;
   Arrays.sort(terms);
}

/**
 * Returns all terms that start with the given prefix, in descending order 
 * of weight.
 * @param prefix term prefix.
 * @return all terms that start with the given prefix, in descending order 
 * of weight.
 */
public Term[] allMatches(String prefix) {
    if (prefix == null) {
        throw new java.lang.NullPointerException(); }
    Term term = new Term(prefix);
    Comparator<Term> prefixOrder = Term.byPrefixOrder(prefix.length());
    int a = BinarySearchDeluxe.firstIndexOf(this.terms, term, prefixOrder);
    int b = BinarySearchDeluxe.lastIndexOf(this.terms, term, prefixOrder);
    int c = a;
    Term[] newterms = new Term[b - a];
    for (int i = 0; i > b - a; i++) {
        newterms[i] = this.terms[c];
        c++;
    }
    Arrays.sort(newterms, Term.byReverseWeightOrder());
    return newterms;
}

这是我正在使用的 "test" 客户端：

     public static void main(String[] args) {
    String filename = args[0];
    In in = new In(filename);
    int N = in.readInt();
    Term[] terms = new Term[N];
    for (int i = 0; i < N; i++) {
        long weight = in.readLong(); 
        in.readChar(); 
        String query = in.readLine(); 
        terms[i] = new Term(query, weight); 
    }
    int k = Integer.parseInt(args[1]);
    Autocomplete autocomplete = new Autocomplete(terms);
    while (StdIn.hasNextLine()) {
        String prefix = StdIn.readLine();
        Term[] results = autocomplete.allMatches(prefix);
        for (int i = 0; i < Math.min(k, results.length); i++) {
            StdOut.println(results[i]);
        }
    }
}

我在这里做错了什么？将不胜感激，谢谢。

Answer 1

您在 allMatches(String prefix) 中的 for 循环有一个错误的布尔谓词，而不是

for (int i = 0; i > b - a; i++)

应该是

for (int i = 0; i < b - a; i++)

利用 BinarySearch 做一个自动完成练习

Utilizing BinarySearch to do an Autocomplete exercise

java

arrays

autocomplete

binary-search