如何查找以排序的ArrayList中的子字符串開頭的元素？

Question

我有一個使用java的33000個元素的排序數組列表，我怎樣才能列出以子串開頭的元素。

例如： 我有一個字符串「空氣」。因此，我需要以「空氣」（「飛機」，「空軍」，「航空公司」等）開頭的每一個字

有沒有辦法做到這一點，而不是一個接一個迭代？

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))及切分是O(K)其中K是子表中的「空氣」的長度（數字 - 前綴詞）。所以，這應該比遍歷列表好得多，至少在不同的前綴上分割（最壞的情況是所有的單詞都以前綴開頭）。

Answer 2

如果您不知道以「air」開頭的元素數目，則您的搜索將按照O（n）的順序進行。沒有蠻力方法或平衡樹搜索，您可以執行以小於O（n）達到此目的。

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

     } 

    }