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二進制搜索更多的一個結果？

回答

相關問題