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

У меня есть список отсортированных объектов, и я хочу найти первое вхождение и последнее вхождение объекта. В С++ я могу легко использовать 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;

Ответы

Ответ 1

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

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

Ответ 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 first appeareance on position " 
            + first + "and it 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);
        }

}

Ответ 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;
}

Ответ 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, аналогичная С++. Обратите внимание, что элемент, который вы ищете, не должен присутствовать в векторе или списке. Эта реализация дает только верхнюю и нижнюю границы элемента.

Ответ 5

Просто используйте бинарный поиск

private static int lowerBound(int[] a, int low, int high, int element){
    while(low < high){
        int middle = low + (high - low)/2;
        if(element > a[middle])
            low = middle + 1;
        else 
            high = middle;
    }
    return low;
}


private static int upperBound(int[] a, int low, int high, int element){
    while(low < high){
        int middle = low + (high - low)/2;
        if(a[middle] > element)
            high = middle;
        else 
            low = middle + 1;
    }
    return low;
}

Ответ 6

Java уже имеет встроенную функцию двоичного поиска, которая вычисляет нижнюю/верхнюю границы для элемента в массиве, нет необходимости реализовывать пользовательские методы.

Когда мы говорим о верхних/нижних границах или равных диапазонах, мы всегда имеем в виду индексы контейнера (в данном случае ArrayList), а не содержащиеся в нем элементы. Давайте рассмотрим массив (мы предполагаем, что массив отсортирован, иначе мы сначала отсортируем его):

List<Integer> nums = new ArrayList<>(Arrays.asList(2,3,5,5,7,9,10,18,22));

Функция "нижняя граница" должна возвращать индекс массива, где элемент должен быть вставлен в , чтобы массив был отсортирован. "Верхняя граница" должна возвращать индекс наименьшего элемента в массиве, который больше, чем искомого элемента. Например,

lowerBound(nums, 6)

должен возвращать 3, потому что 3 - это позиция массива (начиная отсчет с 0), где 6 должно быть вставлено для сохранения сортировки массива.

upperBound(nums, 6)

должен возвращать 4, потому что 4 - это позиция наименьшего элемента smallest в массиве, то есть больше, чем 5 или 6 (номер 7 в позиции 4).

В C++ в стандартной библиотеке оба алгоритма уже реализованы в стандартной библиотеке. В Java вы можете использовать

Collections.binarySearch(nums, element)

для вычисления положения в сложности логарифмического времени.

Если массив содержит элемент, Collections.binarySearch возвращает первый индекс элемента (в массиве выше 2). В противном случае он возвращает отрицательное число, которое указывает позицию в массиве следующего большего элемента, , считая в обратном направлении от последнего индекса массива. Число, найденное в этой позиции, является наименьшим элементом массива , который больше, чем искомый элемент.

Например, если вы позвоните

int idx = Collections.binarySearch(nums, 6)

функция возвращает -5. Если вы посчитаете в обратном направлении от последнего индекса массива (-1, -2,...), индекс -5 будет указывать на число 7 - наименьшее число в массиве, которое больше, чем элемент 6.

Заключение: если отсортированный массив содержит искомый элемент, нижняя граница - это позиция элемента, а верхняя граница - это позиция следующего большего элемента.

Если массив не содержит элемента, нижняя граница - это позиция

Math.abs(idx) - 2

и верхняя граница - это позиция

Math.abs(idx) - 1

где

idx = Collections.binarySearch(nums, element)

И, пожалуйста, всегда помните о пограничных случаях. Например, если вы ищете 1 в указанном выше массиве:

idx = Collections.binarySearch(nums, 1)

Функция возвращается -1. Итак, upperBound = Math.abs(idx) - 1 = 0 - элемент 2 в позиции 0. Но нет нижней границы для элемента 1, потому что 2 - это наименьшее число в массиве. Та же логика применима к элементам, которые больше самого большого числа в массиве: если вы посмотрите на нижнюю/верхнюю границы числа 25, вы получите

  idx = Collections.binarySearch(nums, 25)

ix = -1 0. Вы можете рассчитать нижнюю границу: lb = Math.abs(-1 0) - 2 = 8, то есть последний индекс массива, но нет верхней границы, потому что 22 уже самый большой элемент в массиве и там нет элемента в позиции 9.

Параметр equal_range указывает все индексы массива в диапазоне, начиная с индекса нижней границы до (но не включая) верхней границы. Например, равный диапазон числа 5 в приведенном выше массиве - это индексы

 [2,3]

Равный диапазон числа 6 пуст, потому что в массиве нет числа 6.