Java二进制搜索更多的一个结果？

我对二分查找有疑问。我在那里我使用这个搜索列表中的字符串与前缀strting一个ArrayList：Java二进制搜索更多的一个结果？

if(prefix.length()>1){ 
     prefixlow=prefix.toLowerCase(); 
     int n = Collections.binarySearch(words, prefixlow); 
     if (n < 0 && -n <= words.size()) { 
      String match = words.get(-n - 1); 
      if (match.startsWith(prefixlow)) { 
       // A completion is found 
       completion = match.substring(0+prefix.length()); 

       keyboardwindow.jTextArea1.setText(prefix+completion); 
      } 
     } 
     else{keyboardwindow.jTextArea1.setText(prefix);} 
    }

现在，这只是寻找我一个结果。下一步是从列表中获得所有从这个前缀开始的单词，而不仅仅是一个单词。所以第一个问题是，它总是会找到以前缀开头的第一个单词吗？因为我认为它给了你一个随机的字符串，只是从前缀开始......所以任何tipps我如何获得以我的前缀开始的字符串的起始位置和结束位置？

来源

2017-06-21 QFireball

通过List<String>的二进制搜索将找到您正在查找的确切前缀的索引。如果您的前缀中多次出现的List（而不是更长String个前缀，而是作为整个String），你会得到这些出场的一个（不一定是第一个）的指数。

但是，它看起来像你不期望你正在寻找的前缀出现在List（作为整个String），这就是为什么你期望返回负指标。

在这种情况下，根据元素的自然顺序，binarySearch()将返回前缀在List中出现的索引的负值。

由于字符串的自然顺序是字典顺序，前缀会出现在任何再String s表示与该前缀开头。因此，您可以简单地迭代List，从-n - 1开始，并获得以您的前缀开头的所有String。

例如：

List<String> binSearch = Arrays.asList ("aaa","aab","aac","bba","bbb","bbbb","c"); 
System.out.println ("-n-1 = " + (-Collections.binarySearch (binSearch, "bb")-1));

此打印：

-n-1 = 3

3是索引在该前缀 “BB” 本来（如果当时存在于List），但由于它不在列表中，您知道所有以“bb”开头的String都位于索引> = 3处。

因此，您的代码可以修改用循环替换if (match.startsWith(prefixlow))条件D：

if(prefix.length()>1) { 
    prefixlow=prefix.toLowerCase(); 
    int n = Collections.binarySearch(words, prefixlow); 
    if (n < 0 && -n <= words.size()) { 
     String firstMatch = words.get(-n - 1); 
     int i = -n - 1; 
     String match = null; 
     while (i < words.size() && (match = words.get(i)).startsWith(prefixlow)) { 
      // A completion is found 
      completion = match.substring(prefix.length()); 
      keyboardwindow.jTextArea1.setText(prefix+completion); 
      i++; 
     } 
    } else { 
     keyboardwindow.jTextArea1.setText(prefix); 
    } 
}

来源

2017-06-21 07:38:09 Eran

这种解决方案我收到此错误按摩java.lang.IndexOutOfBoundsException：指数：24，大小：24编辑：哦确定的，因为我的洞名单开始的前缀，但是，所以我需要停止循环的时候，他是在最后一个元素 – QFireball

oh thx为此 – QFireball

你是正确的在这里，你会得到与搜索到的前缀一个随机字符串。但数组进行排序，所以你可以在两个方向上从创建索引执行互为作用，而（yourPrefix匹配其他字符串的前缀）。这将为您提供起始和结束索引。

来源

2017-06-21 07:41:57

Java二进制搜索更多的一个结果？

回答

相关问题