Javaバイナリ検索の結果が1つ多いですか？

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

は今、これはちょうど私の1件の結果を見つけることです：私は私が接頭辞でstrting文字列をリストを検索するためにこれを使用ArrayListのを持っています。次のステップは、この接頭辞で始まるリストからすべての単語を1つだけでなく取得することです。だから最初の質問は、これは常に接頭辞で始まる最初の単語を見つけるのですか？私はそれがあなたに接頭辞で始まるランダムな文字列を与えると思うので...どのようなtipps私はどのように私の接頭辞で始まる文字列の開始位置と終了位置を取得する？

Answer 1

List<String>を超えるバイナリ検索では、探している接頭辞の正確なオカレンスのインデックスが見つかります。プレフィックスがに複数回表示されている場合（プレフィックスはString秒ではなく、String全体）、これらのプレースメントのインデックスが表示されます（必ずしも最初のものでなくてもかまいません）。

しかし、List（全体ではString）に表示する必要があるプレフィックスがないと思われるため、負のインデックスが返されることが予想されます。

この場合、binarySearch()は、要素の自然順序付けに従って、接頭辞が現れたインデックスの負の値をListに返します。

Stringsの自然順序は辞書順であるため、その接頭辞で始まる接頭辞はより長くなる前に来ます。Stringしたがって、簡単に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); 
    } 
} 

Answer 2

、あなたが検索接頭辞を持つランダムな文字列を取得します。しかし、配列はソートされているので、見つかったインデックスから両方向への介入を実行できます（yourPrefixは他の文字列の接頭辞と一致します）。それはあなたに開始と終了のインデックスを取得します。