É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 Java, vous utilisez Collections.binarySearch pour trouver la borne inférieure de la plage égale dans une liste triée (Arrays.binarySearch fournit une fonctionnalité similaire pour les tableaux). Cela vous donne une position dans la plage égale sans autres garanties :

Si la liste contient plusieurs éléments égaux à l'objet spécifié, il n'y a aucune garantie quant à celui qui sera trouvé.

Ensuite, vous itérez linéairement vers l'avant puis vers l'arrière jusqu'à ce que vous atteigniez la fin de la plage égale.

Ces méthodes fonctionnent pour les objets implémentant l'interface Comparable. Pour les classes qui n'implémentent pas Comparable, vous pouvez fournir une instance d'un custom Comparator pour comparer les éléments de votre type spécifique.

Answer 2

Nous pouvons trouver la borne inférieure et la borne supérieure à l'aide de la fonction de bibliothèque java ainsi qu'en définissant notre propre Fonction LowerBound et UpperBound.

{#cas-1}

si le nombre n'est pas présent la borne inférieure et la borne supérieure sera la même. c'est-à-dire dans ce cas lb et ub sera le point d'insertion du tableau, c'est-à-dire le point où le nombre doit être inséré pour garder le tableau trié.

Exemple-1:

6 1 // 6 est la taille du tableau et 1 est la clé
2 3 4 5 6 7 ici lb=0 et ub=0 (0 est la position où 1 devrait être inséré pour garder le tableau trié)

6 8 // 6 est la taille du tableau et 8 est la clé
2 3 4 5 6 7  ici lb=6 et ub=6 (6 est la position où 8 devrait être inséré pour garder le tableau trié)

6 3 // 6 est la taille du tableau et 3 est la clé
1 2 2 2 4 5  ici lb=4 et ub=4 (4 est la position où 3 devrait être inséré pour garder le tableau trié)

{#cas-2(a)}

si le nombre est présent et a une fréquence de 1. c'est-à-dire le nombre d'occurrences est de 1

lb\=indice de ce nombre.
ub\=indice du nombre suivant qui est légèrement supérieur à ce nombre dans le tableau c'est-à-dire ub\=indice de ce nombre+1

Exemple-2:

6 5 // 6 est la taille du tableau et 5 est la clé
1 2 3 4 5 6 ici lb=4 et ub=5

{#cas-2(b)}

Si le nombre est présent et a une fréquence supérieure à 1. le nombre est apparu plusieurs fois. dans ce cas lb serait l'index de la 1ère occurrence de ce nombre. ub serait l'index de la dernière occurrence de ce nombre+1. c'est-à-dire l'indice de ce nombre qui est légèrement supérieur à la clé dans le tableau.

Exemple-3:

 11 5 // 11 est la taille du tableau et 5 est la clé
 1 2 3 4 5 5 5 5 5 7 7 ici lb=4 et ub=9

Mise en œuvre de Lower_Bound et Upper_Bound

Méthode-1: Par fonction de bibliothèque

// a est le tableau et x est la valeur cible

int lb=Arrays.binarySearch(a,x); // pour la borne inférieure

int ub=Arrays.binarySearch(a,x); // pour la borne supérieure

if(lb<0) {lb=Math.abs(lb)-1;}//si le nombre n'est pas présent

else{ // si le nombre est présent nous vérifions 
    //si le nombre est présent plusieurs fois ou non
    int y=a[lb];
    for(int i=lb-1; i>=0; i--){
        if(a[i]==y) --lb;
        else break;
    }
}
  if(ub<0) {ub=Math.abs(ub)-1;}//si le nombre n'est pas présent

  else{// si le nombre est présent nous vérifions 
    //si le nombre est présent plusieurs fois ou non
    int y=a[ub];
    for(int i=ub+1; i

``

Méthode-2: En définissant sa propre fonction

//pour la borne inférieure

static int LowerBound(int a[], int x) { // x est la valeur cible ou la clé
  int l=-1,r=a.length;
  while(l+1>>1;
    if(a[m]>=x) r=m;
    else l=m;
  }
  return r;
}

// pour la Borne_Supérieure

 static int UpperBound(int a[], int x) {// x est la clé ou la valeur cible
    int l=-1,r=a.length;
    while(l+1>>1;
       if(a[m]<=x) l=m;
       else r=m;
    }
    return l+1;
 }

ou nous pouvons utiliser

int m=l+(r-l)/2;

mais si nous utilisons

int m=(l+r)>>>1; // c'est probablement plus rapide

mais l'utilisation de l'une des formules ci-dessus pour calculer m empêchera le débordement

En C et C++ (>>>) l'opérateur est absent, nous pouvons faire ceci:

int m= ((unsigned int)l + (unsigned int)r)) >> 1;

// implémentation dans le programme:

import java.util.*;
import java.lang.*;
import java.io.*;
public class Lower_bound_and_Upper_bound {

public static void main (String[] args) throws java.lang.Exception
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer s = new StringTokenizer(br.readLine());
    int n=Integer.parseInt(s.nextToken()),x=Integer.parseInt(s.nextToken()),a[]=new int[n];
    s = new StringTokenizer(br.readLine());
    for(int i=0; i

`

# Code C++ équivalent pour calculer la borne inférieure et la borne supérieure

  #include
  #define IRONMAN ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  using namespace std;
  typedef long long int ll;
  int main() {
    IRONMAN
    int n,x;cin>>n>>x;
    vector v(n);
    for(auto &i: v) cin>>i;
    ll lb=(lower_bound(v.begin(),v.end(),x))-v.begin();// pour calculer lb
    ll ub=(upper_bound(v.begin(),v.end(),x))-v.begin();// pour calculer ub
    cout<

` ``

Answer 3

Java a déjà une fonction de recherche binaire intégrée qui calcule les bornes inférieures/supérieures pour un élément dans un tableau, il n'est pas nécessaire d'implémenter des méthodes personnalisées.

Lorsque nous parlons de bornes supérieures/inférieures ou de plages égales, nous voulons toujours dire les index d'un conteneur (dans ce cas d'ArrayList), et non les éléments contenus. Considérons un tableau (nous supposons que le tableau est trié, sinon nous le trions d'abord) :

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

La fonction de "borne inférieure" doit retourner l'index du tableau, où l'élément doit être inséré pour garder le tableau trié. La "borne supérieure" doit retourner l'index du plus petit élément dans le tableau, qui est plus grand que l'élément recherché. Par exemple

lowerBound(nums, 6)

doit retourner 3, car 3 est la position du tableau (en commençant à compter à partir de 0), où 6 doit être inséré pour garder le tableau trié.

La

upperBound(nums, 6)

doit retourner 4, car 4 est la position du plus petit élément dans le tableau, qui est plus grand que 5 ou 6, (le numéro 7 à la position 4).

En C++ dans la bibliothèque standard les deux algorithmes sont déjà implémentés dans la bibliothèque standard. En Java vous pouvez utiliser

Collections.binarySearch(nums, élément)

pour calculer la position en complexité de temps logarithmique.

Si le tableau contient l'élément, Collections.binarySearch retourne le premier index de l'élément (dans le tableau ci-dessus 2). Sinon, cela retourne un nombre négatif qui spécifie la position dans le tableau du prochain élément plus grand, en comptant à rebours à partir du dernier index du tableau. Le nombre trouvé à cette position est le plus petit élément du tableau qui est plus grand que l'élément que vous recherchez.

Par exemple, si vous appelez

int idx = Collections.binarySearch(nums, 6)

la fonction retourne -5. Si vous comptez à rebours à partir du dernier index du tableau (-1, -2, ...) l'index -5 pointe vers le chiffre 7 - le plus petit chiffre dans le tableau qui est plus grand que l'élément 6.

Conclusion : si le tableau trié contient l'élément recherché, la borne inférieure est la position de l'élément, et la borne supérieure est la position du prochain élément plus grand.

Si le tableau ne contient pas l'élément, la borne inférieure est la position

Math.abs(idx) - 2

et la borne supérieure est la position

Math.abs(idx) - 1

où

idx = Collections.binarySearch(nums, élément)

Et veuillez toujours garder à l'esprit les cas limites. Par exemple, si vous cherchez le chiffre 1 dans le tableau spécifié ci-dessus :

idx = Collections.binarySearch(nums, 1)

La fonction retourne -1. Ainsi, la borne supérieure = Math.abs(idx) - 1 = 0 - l'élément 2 à la position 0. Mais il n'y a pas de borne inférieure pour l'élément 1, car 2 est le plus petit chiffre dans le tableau. La même logique s'applique aux éléments plus grands que le plus grand chiffre dans le tableau : si vous cherchez les bornes inférieures/supérieures du chiffre 25, vous obtiendrez

  idx = Collections.binarySearch(nums, 25) 

ix = -10. Vous pouvez calculer la borne inférieure : lb = Math.abs(-10) - 2 = 8, c'est la dernière index du tableau, mais il n'y a pas de borne supérieure, car 22 est déjà le plus grand élément dans le tableau et il n'y a pas d'élément à la position 9.

L'équivalent_range spécifie tous les index du tableau dans la plage à partir de l'index de la borne inférieure jusqu'à (mais non inclus) la borne supérieure. Par exemple, l'équivalent_range du chiffre 5 dans le tableau ci-dessus sont les index

 [2,3]

L'équivalent_range du chiffre 6 est vide, car il n'y a pas de chiffre 6 dans le tableau.

Answer 4

L'équivalent Java de lower_bound en cpp est

public static int lower(int arr[],int key){
    int low = 0;
    int high = arr.length-1;
    while(low < high){
        int mid = low + (high - low)/2;
        if(arr[mid] >= key){
            high = mid;
        }
        else{
            low = mid+1;
        }
    }
    return low;
}

Mais le snippet ci-dessus donnera la limite inférieure si la clé n'est pas présente dans le tableau

L'équivalent Java de upper_bound en cpp est

public static int upper(int arr[],int key){
    int low = 0;
    int high = arr.length-1;
    while(low < high){
        int mid = low + (high - low+1)/2;
        if(arr[mid] <= key){
            low = mid;
        }
        else{
            high = mid-1;
        }
    }
    return low;
}

Mais le snippet ci-dessus donnera la limite inférieure de la clé si la clé n'est pas présente dans le tableau

Answer 5

Vous pouvez essayer quelque chose comme ceci:

public class TestSOF {

    private ArrayList  testList = new ArrayList ();
    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("L'élément " + element + " a sa première apparition à la position " 
        + first + "et sa dernière à la position " + last);
        }

        else{

             System.out.println("Votre élément " + element + " n'est pas dans la arraylist!");
       }
    }

    public static void main (String [] args){

        TestSOF testSOF = new TestSOF();

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