binary search - 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()) << '
';

  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;

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.