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;
Best Answer
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: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 theComparable
, you can supply an instance of a customComparator
for comparing the elements of your specific type.