如何查找以排序的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)); 

     } 

    }