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

Question

我有一个问题要进行二进制搜索。我有一个数组列表，我使用它在列表中搜索带有前缀的字符串：

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);}
} 

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

Answer 1

对List<String>进行二叉搜索将找到您要查找的前缀的确切匹配项的索引。如果您的前缀在List中多次出现(不是作为较长的Strings 的前缀，而是作为整个String)，您将获得其中一个出现的索引(不一定是第一个)。

但是，看起来您不希望要查找的前缀出现在List中(作为整个String)，这就是您希望返回负索引的原因。

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

由于字符串的自然顺序是字典顺序，因此前缀将出现在以该前缀开头的任何String之前。因此，您可以简单地从-n - 1开始迭代List，并从前缀开始获取所有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))条件替换为循环来修改代码：

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);
}
} 

Answer 2

您在这里是正确的，您将获得一个带有搜索前缀的随机字符串。但是数组是排序的，因此您可以从找到的索引在两个方向上执行交互，而(yourPrefix匹配其他字符串的前缀)。这将为您提供开始和结束索引。