The Apache commons has some good collections utilities but not the lower_bound(), upper_bound() pair.

It is still a mystery why the Java Lib folks decided to ignore this function. The use of it is quite common for look-up tables. Today, I wanted to use these functions to look up for some limit values for input ranges from a table. The easiest way to explain this is that different input ranges require a look-up into a number determined by the range. The ranges are consecutive, say 0-25, 25-50, 50-100,100-500. Each range would map to a number, say 100, 212, 320, 400. The look-up function needs to return the correct number given an input number within a range.

For ex:

10 : 100

25 : 212

30 : 212

200 : 400

To satisfy the lower_bound, upper_bound standard specs, a number below the smallest range (say -10) would map to 100, and a number above the largest range will map to nothing.

lower_bound() should return an index to the first element in the sorted container that is equal to or above the number being looked up, and -1 if there is no such element.

upper_bound() should return an index to the first element in the sorted container that is above the number being looked up, and -1 if there is no such element.

Here are the functions I ended up writing:

```
public static int lower_bound(Comparable[] arr, Comparable key) {
int len = arr.length;
int lo = 0;
int hi = len-1;
int mid = (lo + hi)/2;
while (true) {
int cmp = arr[mid].compareTo(key);
if (cmp == 0 || cmp > 0) {
hi = mid-1;
if (hi < lo)
return mid;
} else {
lo = mid+1;
if (hi < lo)
return mid<len-1?mid+1:-1;
}
mid = (lo + hi)/2;
}
}
public static int upper_bound(Comparable[] arr, Comparable key) {
int len = arr.length;
int lo = 0;
int hi = len-1;
int mid = (lo + hi)/2;
while (true) {
int cmp = arr[mid].compareTo(key);
if (cmp == 0 || cmp < 0) {
lo = mid+1;
if (hi < lo)
return mid<len-1?mid+1:-1;
} else {
hi = mid-1;
if (hi < lo)
return mid;
}
mid = (lo + hi)/2;
}
}
```

Here are the tests:

```
public void test_lower_bound() {
final int arrSize = 500;
final int maxNum = 1000;
Integer[] bArr = new Integer[arrSize];
Random r = new Random();
for (int k=0; k<arrSize; k++) {
bArr[k]=r.nextInt(maxNum);
}
Arrays.sort(bArr);
final int numIter = 2000;
for (int k=0; k<numIter; k++) {
int n = r.nextInt(maxNum);
int j = Utils.lower_bound(bArr, n);
assertTrue((bArr[arrSize-1]<n && j==-1) || (bArr[j]>=n && (j==0 || bArr[j-1]<n)));
}
}
public void test_upper_bound() {
final int arrSize = 500;
final int maxNum = 1000;
Integer[] bArr = new Integer[arrSize];
Random r = new Random();
for (int k=0; k<arrSize; k++) {
bArr[k]=r.nextInt(maxNum);
}
Arrays.sort(bArr);
final int numIter = 2000;
for (int k=0; k<numIter; k++) {
int n = r.nextInt(maxNum);
int j = Utils.upper_bound(bArr, n);
assertTrue((bArr[arrSize-1]<=n && j==-1) || (bArr[j]>n && (j==0 || bArr[j-1]<=n)));
}
}
```