upper_bound and lower_bound in Java Standard Library

Sometimes, there are simple things that fly under your radar.

C++ has upper_bound and lower_bound that return the elements that are bounds for a given element in a sorted array or collection. Python has a similar bisect module that has functions bisect_left and bisect_right.

I did not find similar functions in Java Standard Library. I would resort to following the binary search again over the collection or array to find the bounds. I discovered that the binarySearch methods from java.util.Collections and java.util.Arrays return the index of element if the element was found in the collection/array or a negative number indicating the insertion point of the element.

The insertion point is the clue here. From the Java docs, here is the description of the return value from binarySearch:

index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key.

Also notice here that (-(insertion point) - 1) is actually the two’s complement of insertion point. Applying tilde operator ~ to an integer gives us its 2s complement.

 int upperBound;
 int lowerBound;
 int index = Collections.binarySearch(sortedList);
 if(index < 0) {
	 index = ~index; //Get the insertion point using 2's complement.
 }
 if(index < sortedList.size()) {
	 upperBound = sortedList.get(index);
	 lowerBound = sortedList.get(index - 1);
 }