Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java equivalent of c++ equal_range (or lower_bound & upper_bound)

Tags:

I have a List of object sorted and I want to find the first occurrence and the last occurrence of an object. In C++, I can easily use std::equal_range (or just one lower_bound and one upper_bound).

For example:

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

In Java, there seems to be no simple equivalence? How should I do with the equal range with

List<MyClass> myList;

By the way, I am using a standard import java.util.List;

like image 256
RoundPi Avatar asked Mar 24 '13 20:03

RoundPi


People also ask

How do you calculate lower bound in Java?

You can calculate the lower bound : lb = Math. abs(-10) - 2 = 8, that is the last index of the array, but there is no upper bound, because 22 is already biggest element in the array and there is no element at position 9. Equal range of number 6 is empty, because there is no number 6 in the array.

What is upper bound and lower bound in Java?

The Upper Bounded Wildcards section shows that an upper bounded wildcard restricts the unknown type to be a specific type or a subtype of that type and is represented using the extends keyword. In a similar way, a lower bounded wildcard restricts the unknown type to be a specific type or a super type of that type.

What is the complexity of lower_bound?

Time Complexity of set::lower_bound() is O(logn), where n is the size of the set.

Can we use lower_bound in array?

But in Array of Pairs lower_bound() for pair(x, y) will return an iterator pointing to the position of pair whose the first value is greater than or equals x and second value is greater than equals to y.


2 Answers

In Java, you use Collections.binarySearch to find the lower bound of the equal range in a sorted list (Arrays.binarySearch provides a similar capability for arrays). This gives you a position within the equal range with no further guarantees:

If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found.

Then you iterate linearly forward and then backward until you hit the end of the equal range.

These methods work for objects implementing the Comparable interface. For classes that do not implement the Comparable, you can supply an instance of a custom Comparator for comparing the elements of your specific type.

like image 104
Sergey Kalinichenko Avatar answered Sep 20 '22 10:09

Sergey Kalinichenko


We can find Lower bound and upper bound with the help of java library function as well as by defining our own LowerBound and UpperBound Function.

{#case-1}

if the number is not present both lower bound and upper bound would be same .i.e. in that case lb and ub would be the insertion point of the array i.e. that point where the number should be inserted to keep the array sorted.

Example-1:

6 1 // 6 is the size of the array and 1 is the key
2 3 4 5 6 7 here lb=0 and ub=0 (0 is the position where 1 should be inserted to keep the array sorted)

6 8 // 6 is the size of the array and 8 is the key
2 3 4 5 6 7  here lb=6 and ub=6 (6 is the position where 8 should be inserted to keep the array sorted)

6 3 // 6 is the size of the array and 3 is the key
1 2 2 2 4 5  here lb=4 and ub=4 (4 is the position where 3 should be inserted to keep the array sorted)


    

{#case-2(a)}

if the number is present and have frequency 1. i.e. number of occurrence is 1

lb=index of that number.
ub=index of the next number which is just greater than that number in the array .i.e. ub=index of that number+1

Example-2:

6 5 // 6 is the size of the array and 5 is the key
1 2 3 4 5 6 here lb=4 and ub=5
    

{#case-2(b)}

if the number is present and have frequency more than 1. number is occured multiple times.in this case lb would be the index of the 1st occurrence of that number. ub would be the index of the last occurrence of that number+1. i.e. index of that number which is just greater than the key in the array.

Example-3:

 11 5 // 11 is the size of the array and 5 is the key
 1 2 3 4 5 5 5 5 5 7 7 here lb=4 and ub=9

Implementation of Lower_Bound and Upper_Bound

Method-1: By Library function

// a is the array and x is the target value

int lb=Arrays.binarySearch(a,x); // for lower_bound

int ub=Arrays.binarySearch(a,x); // for upper_bound

if(lb<0) {lb=Math.abs(lb)-1;}//if the number is not present

else{ // if the number is present we are checking 
    //whether the number is present multiple times or not
    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;}//if the number is not present

  else{// if the number is present we are checking 
    //whether the number is present multiple times or not
    int y=a[ub];
    for(int i=ub+1; i<n; i++){
        if(a[i]==y) ++ub;
        else break;
    }
    ++ub;
}

Method-2: By Defining own Function

//for lower bound

static int LowerBound(int a[], int x) { // x is the target value or key
  int l=-1,r=a.length;
  while(l+1<r) {
    int m=(l+r)>>>1;
    if(a[m]>=x) r=m;
    else l=m;
  }
  return r;
}

// for Upper_Bound

 static int UpperBound(int a[], int x) {// x is the key or target value
    int l=-1,r=a.length;
    while(l+1<r) {
       int m=(l+r)>>>1;
       if(a[m]<=x) l=m;
       else r=m;
    }
    return l+1;
 }

     

or we can use

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

but if we use

int m=(l+r)>>>1; // it is probably faster

but the usage of any of the above formula of calculating m will prevent overflow

In C and C++ (>>>) operator is absent, we can do this:

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

// implementation in program:

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<n; i++) a[i]=Integer.parseInt(s.nextToken());
    Arrays.sort(a);// Array should be sorted. otherwise lb and ub cant be calculated
    int u=UpperBound(a,x);
    int l=LowerBound(a,x);
    System.out.println(l+" "+u);
 }
}

# Equivalent C++ code for calculating lowerbound and upperbound

  #include<bits/stdc++.h>
  #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<int> v(n);
    for(auto &i: v) cin>>i;
    ll lb=(lower_bound(v.begin(),v.end(),x))-v.begin();// for calculating lb
    ll ub=(upper_bound(v.begin(),v.end(),x))-v.begin();// for calculating ub
    cout<<lb<<" "<<ub<<"\n";
    return 0;
  }
like image 42
Atish Naskar Avatar answered Sep 20 '22 10:09

Atish Naskar