Équivalent Java de c++ equal_range (ou lower_bound & upper_bound)

Question

J'ai une liste d'objets triée et je veux trouver la première occurrence et la dernière occurrence d'un objet. En C++, je peux facilement utiliser std::equal_range (ou juste une lower_bound et une upper_bound).

Par exemple:

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

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector v(myints,myints+8);                         // 10 20 30 30 20 10 10 20
  std::pair::iterator,std::vector::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;
}

En Java, il semble ne pas y avoir d'équivalence simple? Comment devrais-je faire avec l'égalité range avec

List myList;

Au fait, j'utilise une importation standard java.util.List;

Answer 1

En recherche binaire, lorsque vous trouvez l'élément, vous pouvez continuer à faire une recherche binaire vers la gauche pour trouver la première occurrence et vers la droite pour trouver le dernier élément. L'idée devrait être claire avec le code :

/*
B: élément à trouver la première ou la dernière occurrence de
searchFirst: true pour trouver la première occurrence, false pour trouver la dernière
 */
Integer bound(final List A, int B, boolean searchFirst){
    int n = A.size();
    int low = 0;
    int high = n-1;
    int res = -1;   // si l'élément n'est pas trouvé
    int mid ;
    while(low<=high){
        mid = low+(high-low)/2;
        if(A.get(mid)==B){
            res=mid;
            if(searchFirst){high=mid-1;}    // pour trouver le premier, aller à gauche
            else{low=mid+1;}                // pour trouver le dernier, aller à droite
        }
        else if(B>A.get(mid)){low=mid+1;}
        else{high=mid-1;}
    }
    return res;
}

Answer 2

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

}

This is the implementation for lower_bound and upper_bound similar to c++. Note that the element you are searching for need not be present in the vector or list. This implementation only gives the element's upper and lower bounds.

Answer 3

Essayez de cette manière, pour les bornes inférieures et supérieures. C'est facile à implémenter.

import java.util.Arrays;

class LowerBoundUpperBound{
    public static void main(String[] args) {
        int a[] = {1, 2, 3, 4, 5, 5, 5, 5, 5, 7, 7};

        int key = 5;
        int pos = Arrays.binarySearch(a, key);
        int lb = (pos < 0) ? ~pos - 1 : getlb(pos, a);
        int ub = (pos < 0) ? ~pos : getUb(pos, a);

        System.out.println("Seuil inférieur=" + lb);
        System.out.println("Seuil supérieur=" + ub);

        // Vous pouvez également essayer avec a[] = {1, 2, 3, 4, 5, 6};
        // Pour key=5, lb=3 et ub=5

    }

    private static int getlb(int pos, int[] a) {
        while (pos - 1 >= 0 && a[pos] == a[pos - 1]) pos--;
        return pos - 1;
    }

    private static int getUb(int pos, int[] a) {
        while (pos + 1 < a.length&&a[pos]==a[pos+1]) pos++;
        return pos+1;

    }
}

Remarque: Le tableau doit être trié lors de l'exécution de la méthode ci-dessus.

Answer 4

Si vous souhaitez trouver lower_bound sans définir votre propre méthode et tout faire à partir de zéro, utilisez le code suivant. Comme vous l'avez peut-être remarqué, cette méthode fonctionne uniquement avec des tableaux primitifs et non avec ArrayList car nous n'avons pas de fonction dans la classe Collections pour spécifier l'index de début et de fin pour Binarysearch (à partir de java16).

• al est un tableau (String[] al = new String[N];)

• token est ce que nous cherchons dans le tableau.

  Arrays.sort(al, 0, N); int index = Arrays.binarySearch(al, 0, N , token); while(index > 0 && al[index].equals(al[index - 1])){ index = Arrays.binarySearch(al, 0, index, token); //lower_bound in java. }

Pour upper bound vous pouvez facilement modifier le code.