ソートされたArrayList内のサブ文字列で始まる要素を見つけるにはどうすればよいですか？

Question

javaを使用して33000要素のソートされたarrayListを持っていますが、どのように部分文字列で始まる要素のみをリストすることができますか？

例： 文字列「air」があります。だから私は "空気"（ "飛行機"、 "空軍"、 "航空会社"など）から始まるすべての単語が必要です

これを行う方法はありますか？

Answer 1

だから、あなたが行うことができます、あなたがArrayList<String>wordsをソートしている与えられた：

String prefix = "air"; 
int start = Collections.binarySearch(words, prefix); 
// index of prefix OR -(insertion point) - 1 
if (start < 0) // prefix is not contained as a whole word 
    start = -start - 1; 
int end = start; 
while (end < words.size() && words.get(end).startsWith(prefix)) 
    end++; 
List<String> prefixWords = words.subList(start, end); 

バイナリ検索がO(log(N))で、スライスがKは「空気」のサブリストの長さ（数あるO(K)です - 接頭語）。したがって、これはリストを反復するよりはるかに優れているはずです。少なくとも、異なる接頭辞（すべての語が接頭辞で始まるという最悪のケース）で解消されます。

Answer 2

手前に "air"で始まる要素の数がわからない場合、検索はO（n）のオーダーになります。 O（n）未満でこれを達成するために実行できるブルートフォース方式またはバランスツリー検索はありません。あなたが左に向けて、リスト上のインデックスの反復を持って、あなたがリストの最後にヒット右のいずれかになるまで/から始まるまたは1つのyoureの異なるプレフィックスが検索した後

Answer 3

はバイナリ検索が続いて

public static int binarySearch(ArrayList<String> sortedArray,String find){ 
     int lowerBound=0; 
     int upperBound=sortedArray.size()-1; 

     while(true){ 
      int midIndex=lowerBound+((upperBound-lowerBound)/2); 
      String curr=sortedArray.get(midIndex); 
      if(upperBound<lowerBound){ 
       System.out.println("word not found"); 
       return -1; 
      } 

      if (curr.equals(find)) 
       return midIndex; 

      if(curr.compareTo(find)>0) 
       upperBound=midIndex-1; 

      if(curr.compareTo(find)<0) 
       lowerBound=midIndex+1; 
     } 
    } 

のように最初の後藤だろう

 public static ArrayList<String> makeList(ArrayList<String> sortedArray,String startingWith){ 
     ArrayList<String> result=new ArrayList<>(); 
     ArrayList<String> temp=new ArrayList<>(sortedArray.size());    

     for(int i=0;i<sortedArray.size();i++){ 
      temp.add(" "); 
     } 

     //copy sortedArray to temp 
     for(String s: sortedArray){ 
      if(s.length()>startingWith.length()) { 
       temp.set(sortedArray.indexOf(s), s.substring(0, startingWith.length())); 
      } else temp.set(sortedArray.indexOf(s),s); 

     } 


     int index=binarySearch(temp,startingWith); 
     result.add(sortedArray.get(index)); 

     int leftIndex=index; 
     int rightIndex=index;   
     while(true){ 

      //if left and right index dont go out of bounds cont. iterating 
      if ((leftIndex - 1) >= 0) leftIndex--; 
      if ((rightIndex + 1) < sortedArray.size()) rightIndex++; 

      //if left and right index are at end of list return 
      if((rightIndex>=sortedArray.size()) && (leftIndex<0)) return result; 

      boolean isLeft; 
      boolean isRight; 

      if(sortedArray.get(leftIndex).length()>startingWith.length()) { 
       isLeft = sortedArray.get(leftIndex).substring(0,startingWith.length()).equals(startingWith); 
      }else isLeft=false; 


      if(sortedArray.get(rightIndex).length()>startingWith.length()) { 
       isRight = sortedArray.get(rightIndex).substring(0,startingWith.length()).equals(startingWith); 
      }else isRight=false; 

      if(!isLeft && !isRight) return result; 


      if(isRight) result.add(sortedArray.get(rightIndex)); 
      if(isLeft) result.add(sortedArray.get(leftIndex)); 

     } 

    }