Java-эквивалент C++ equal_range (или lower_bound & upper_bound)

Question

У меня есть список отсортированных объектов, и я хочу найти первое вхождение и последнее вхождение объекта. В C++ я могу легко использовать std :: equal_range (или только один lower_bound и one upper_bound).

Например:

bool mygreater (int i,int j) { return (i>j); } 

int main() { 
    int myints[] = {10,20,30,30,20,10,10,20}; 
    std::vector<int> v(myints,myints+8);       // 10 20 30 30 20 10 10 20 
    std::pair<std::vector<int>::iterator,std::vector<int>::iterator> bounds; 

    // using default comparison: 
    std::sort (v.begin(), v.end());        // 10 10 10 20 20 20 30 30 
    bounds=std::equal_range (v.begin(), v.end(), 20);   //  ^ ^

    // using "mygreater" as comp: 
    std::sort (v.begin(), v.end(), mygreater);     // 30 30 20 20 20 10 10 10 
    bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); //  ^ ^

    std::cout << "bounds at positions " << (bounds.first - v.begin()); 
    std::cout << " and " << (bounds.second - v.begin()) << '\n'; 

    return 0; 
} 

В Java, кажется, нет простой эквивалентности? Как я должен делать с одинаковым диапазоном с

List<MyClass> myList; 

Кстати, я использую стандартный импорт java.util.List;

Answer 1

В Java вы используете Collections.binarySearch, чтобы найти нижнюю границу равного диапазона в отсортированном списке (Arrays.binarySearch обеспечивает аналогичную возможность для массивов). Затем вы продолжаете итерировать линейно, пока не дойдете до конца равного диапазона.

Эти методы работают для методов, реализующих интерфейс Comparable. Для классов, которые не реализуют Comparable, вы можете предоставить экземпляр пользовательскихComparator для сравнения элементов вашего типа.

Answer 2

Вы можете попробовать что-то вроде этого:

public class TestSOF { 

     private ArrayList <Integer> testList = new ArrayList <Integer>(); 
     private Integer first, last; 

     public void fillArray(){ 

      testList.add(10); 
      testList.add(20); 
      testList.add(30); 
      testList.add(30); 
      testList.add(20); 
      testList.add(10); 
      testList.add(10); 
      testList.add(20); 
     } 

     public ArrayList getArray(){ 

      return this.testList; 
     } 

     public void sortArray(){ 

      Collections.sort(testList); 
     } 

     public void checkPosition(int element){ 

      if (testList.contains(element)){ 

       first = testList.indexOf(element); 
       last = testList.lastIndexOf(element); 

       System.out.println("The element " + element + "has it's first appeareance on position " 
      + first + "and it's last on position " + last); 
      } 

      else{ 

       System.out.println("Your element " + element + " is not into the arraylist!"); 
      } 
     } 

     public static void main (String [] args){ 

      TestSOF testSOF = new TestSOF(); 

      testSOF.fillArray(); 
      testSOF.sortArray(); 
      testSOF.checkPosition(20); 
     } 

}

Answer 3

В бинарном поиске, когда вы находите элемент, то вы можете продолжать делать бинарный поиск слева от него, чтобы найти первое вхождение и в чтобы найти последний элемент. Идея должна быть ясно с кодом:

/* 
B: element to find first or last occurrence of 
searchFirst: true to find first occurrence, false to find last 
*/ 
Integer bound(final List<Integer> A,int B,boolean searchFirst){ 
    int n = A.size(); 
    int low = 0; 
    int high = n-1; 
    int res = -1; //if element not found 
    int mid ; 
    while(low<=high){ 
     mid = low+(high-low)/2; 
     if(A.get(mid)==B){ 
      res=mid; 
      if(searchFirst){high=mid-1;} //to find first , go left 
      else{low=mid+1;}    // to find last, go right 
     } 
     else if(B>A.get(mid)){low=mid+1;} 
     else{high=mid-1;} 
    } 
    return res; 
} 

Answer 4

import java.io.BufferedReader; 
import java.io.BufferedWriter; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.io.OutputStreamWriter; 
import java.util.Collections; 
import java.util.Vector; 

public class Bounds { 

    public static void main(String[] args) throws IOException { 
     Vector<Float> data = new Vector<>(); 
     for (int i = 29; i >= 0; i -= 2) { 
      data.add(Float.valueOf(i)); 
     } 
     Collections.sort(data); 
     float element = 14; 
     BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); 
     BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out)); 
     String string = bf.readLine(); 
     while (!string.equals("q")) { 
      element=Float.parseFloat(string); 
      int first = 0; 
      int last = data.size(); 
      int mid; 
      while (first < last) { 
       mid = first + ((last - first) >> 1); 
       if (data.get(mid) < element) //lower bound. for upper use <= 
        first = mid + 1; 
       else 
        last = mid; 
      } 
      log.write("data is: "+data+"\n"); 
      if(first==data.size()) 
       first=data.size()-1; 
      log.write("element is : " + first+ "\n"); 
      log.flush(); 
      string= bf.readLine(); 
     } 
     bf.close(); 
    } 

} 

Это реализация для lower_bound и UPPER_BOUND похож на C++. Обратите внимание, что элемент, который вы ищете, не обязательно должен присутствовать в векторе или списке. Эта реализация дает только верхнюю и нижнюю границы элемента.