Having read this question and its answers, I came to the conclusion that there are no standard implementations of those two algorithms. Some background first, though:
Most of us are familiar with binarySearch. The idea is, given a sorted array (or Collection, if using the search facilities from that class), it efficiently (in logarithmic - O(log2n) time) finds the position of a given element in the array/collection. The particular link I provided consists of the following documentation:
[...] If the array contains multiple elements with the specified value, there is no guarantee which one will be found.
Sometimes, we do not care whether we found (or failed to find) the first or the last occurrence of the element we're interested in. But what if we do care?
If we do care, we use variations of the binary search called lower bound and upper bound. They return the first and the last1 occurrence of the given element, respectively.
I come from C++ background and I really love the fact that I can use std::lower_bound and std::upper_bound (and their member function versions for containers that maintain the ordering, e.g. std::map or std::set) on containers.
The simplest use case is, given a sorted collection, determinate how many elements equal to some x are there. This answer from the question I originally linked contains the following:
[After performing a binarySearch] Then you continue iterating linearly until you hit to the end of the equal range.
The problem is that this operation is linear and, for collections with random-access, we can do much better - we can use lower bound and upper bound, then subtract the returned indexes and we get the result in logarithmic, rather than linear, time.
Essentially, it amazes me that there could be no upper- and lower-bound algrithms implemented in Java. I get that I can implement them easily myself, but, for example, what if my data is stored in a TreeMap or TreeSet? They are not random-access but given their implementation, upper- and lower-bounds could be easily implemented as their methods.
Finally, my question is - are there implementations of upper bound and/or lower bound in Java, preferably efficient regarding TreeSet and TreeMap?
1That depends on the convention, though. In C++, upper bound returns the first element that is greater than the element looked for.
Isn't TreeSet.floor() and TreeSet.ceiling() what you're asking for?
Or, alternatively, higher() and lower(), if you wish to exclude equality.