.get（）および.size（）のみを使用して、順序付きArrayListで部分一致をカウントします。

Question

このコードは、指定された接頭辞および接尾辞を持つリスト（ソートされたカスタム配列リスト）の要素の数を返します。それは動作しますが、log（n）+ kのコストがかかります。ここで、kはリスト内でその接頭辞を持つ文字列の数です。とにかくそれをより効率的かつ高速にするには？

//StringList,custom ArrayList only contains size() and get() 
public int countMatches(StringList a, String prefix, String suffix) { 

    int count = 0; 

    for (int i = 0; i < a.size(); i++) { 
     String temp = a.get(i); 
     if (temp.startsWith(prefix) && temp.endsWith(suffix)) { 
      count++; 
     } 
    } 
    return count; 
} 

更新： これは、コードでバイナリ検索は最初の接頭辞を発見した後、コードは接頭辞を持たない単語を取り除くことになっています。しかし、それは動作しません、どのように来るのですか？

 for (int i = low; i < high; i++) { 

      if (!(prefix.compareTo(a.get(i)) > 0)) { 
       high = i; 
       break; 
      } 
     } 

Answer 1

リストがソートされている場合は、binary searchを実行して接頭辞で始まる最初の文字列を見つけることができます。