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

8

2

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;

Gob00st

Posted 2013-03-24T20:50:18.023

Reputation: 3 351

For those of us who don't speak "C", could you describe what you want in English with examples? – Bohemian – 2013-03-24T21:05:35.470

Answers

5

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). Then you continue iterating linearly until you hit to the end of the equal range.

These methods work for methods 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.

dasblinkenlight

Posted 2013-03-24T20:50:18.023

Reputation: 606 616

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>) – Gob00st – 2013-03-24T21:14:26.760

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. – Gob00st – 2013-03-24T21:16:32.427

@Gob00st Take a look at the update to the answer. – dasblinkenlight – 2013-03-24T21:18:58.663

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... – Gob00st – 2013-03-25T01:06:10.330

@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. – dasblinkenlight – 2013-03-25T01:13:21.427

Then what should I do with Java ! – Gob00st – 2013-03-25T01:16:47.120

see my other post here to illustrate this issue - http://stackoverflow.com/questions/15606219/java-collection-binarysearch-not-working-properly

– Gob00st – 2013-03-25T01:17:26.577

0

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

}

Survivor

Posted 2013-03-24T20:50:18.023

Reputation: 554

I need to use customized comparator... – Gob00st – 2013-03-25T01:18:25.597

0

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

RJN_WLY

Posted 2013-03-24T20:50:18.023

Reputation: 50

Careful with that mid=(low+high)/2 line. It can overflow: http://googleresearch.blogspot.mx/2006/06/extra-extra-read-all-about-it-nearly.html

– frozenkoi – 2015-07-30T03:11:13.490

0

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.

UserX

Posted 2013-03-24T20:50:18.023

Reputation: 532