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

Question

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;

Blanketing

For those of us who don't speak "C", could you describe what you want in English with examples? – Westerfield

Answer 1

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.

Worldlywise

Thanks but it seems my List is not compatible with it ? why ?The method binarySearch(List<? extends T>, T, Comparator<? super T>) in the type Collections is not applicable for the arguments (List<MyDerivedData>, Date, Comparator<BaseData>) – Blanketing

I have tried to move the comparator to the Derived class MyDerivedData, but still I am having this problem. My List is simply defined as List<MyDerivedData> myList; Is here a problem ? thanks a lot. – Blanketing

I have tried it but it seems the binary search not returning the only the 1st matching element. Meaning when there is duplicate value, binary search returning random one of the same element... – Blanketing

@Gob00st You are right, I re-read the docs, and it looks like the algorithm makes no guarantees as to the location of the returned value within an equal range. – Worldlywise

Then what should I do with Java ! – Blanketing

see my other post here to illustrate this issue - #15606719 – Blanketing

This is not true. Arrays.sort returns first index that matches the key. It's not guaranteed to be lower bound or upper bound. – Caracal

Your suggested algorithm is linear, not logarithmic, unfortunately. Consider very long range of equal elements. Good luck finding beginning by iteration. – Correll

Answer 2

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

Donnell

Answer 3

Java have already built-in binary search functionality that calculates lower/upper bounds for an element in an array, there is no need to implement custom methods.

When we speak about upper/lower bounds or equal ranges, we always mean indexes of a container (in this case of ArrayList), and not the elements contained. Let's consider an array (we assume the array is sorted, otherwise we sort it first):

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

The "lower bound" function must return the index of the array, where the element must be inserted to keep the array sorted. The "upper bound" must return the index of the smallest element in the array, that is bigger than the looked for element. For example

lowerBound(nums, 6)

must return 3, because 3 is the position of the array (starting counting with 0), where 6 must be inserted to keep array sorted.

The

upperBound(nums, 6)

must return 4, because 4 is the position of the smallest element in the array, that is bigger than 5 or 6, (number 7 on position 4).

In C++ in standard library the both algorithms already implemented in standard library. In Java you can use

Collections.binarySearch(nums, element)

to calculate the position in logarithmic time complexity.

If the array contains the element, Collections.binarySearch returns the first index of the element (in the array above 2). Otherwise it returns a negative number that specifies the position in the array of the next bigger element, counting backwards from the last index of the array. The number found in this position is the smallest element of the array that is bigger than the element you look for.

For example, if you call

int idx = Collections.binarySearch(nums, 6)

the function returns -5. If you count backwards from the last index of the array (-1, -2, ...) the index -5 points to number 7 - the smallest number in the array that is bigger than the element 6.

Conclusion: if the sorted array contains the looked for element, the lower bound is the position of the element, and the upper bound is the position of the next bigger element.

If the array does not contains the element, the lower bound is the position

Math.abs(idx) - 2

and the upper bound is the position

Math.abs(idx) - 1

where

idx = Collections.binarySearch(nums, element)

And please always keep in mind the border cases. For example, if you look for 1 in the above specified array:

idx = Collections.binarySearch(nums, 1)

The functon returns -1. So, the upperBound = Math.abs(idx) - 1 = 0 - the element 2 at position 0. But there is no lower bound for element 1, because 2 is the smallest number in the array. The same logic applies to elements bigger than the biggest number in the array: if you look for lower/upper bounds of number 25, you will get

  idx = Collections.binarySearch(nums, 25) 

ix = -10. 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.

The equal_range specifies all indexes of the array in the range starting from the lower bound index up to (but not including) the upper bound. For example, the equal range of number 5 in the array above are indexes

 [2,3]

Equal range of number 6 is empty, because there is no number 6 in the array.

Payton

Answer 4

Java equivalent of lower_bound in cpp is

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

But the above snippet will give the lower bound if the key is not present in the array

Java equivalent of upper_bound in cpp is

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

But the above snippet will give the lower bound of key if the key is not present in the array

Patagonia

Answer 5

You can try something like this:

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

Rockefeller

Answer 6

In binary search , when you find the element then you can keep doing binary search to its left in order to find first occurrence and to right in order to find last element. The idea should be clear with the code:

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

Promotion

Careful with that mid=(low+high)/2 line. It can overflow: googleresearch.blogspot.mx/2006/06/… – Valuer

Answer 7

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

}

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.

Land

Answer 8

Try in this way, for lower and upper bounds. It is easy to implement.

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("Lower Bound=" + lb);
        System.out.println("Upper Bound=" + ub);

        // You can also try on a[] = {1 ,2 ,3 ,4 ,5 ,6};
        // For key=5, lb=3 and 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;

    }
}

Note: Array must be sorted while performing the above method.

Trilbee

Answer 9

If you want to find lower_bound without defining your own method and do everything from scratch, then use the following code snippet. As you may have noticed, this method works only with primitive arrays not with ArrayList because we do not have a function in Collections class to specify the start and stop index for Binaryserach (as of java16).

• al is an array (String[] al = new String[N];)
• token is what we are looking for in the array.

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

For upper bound you can easily modify the code.

Marge