Why am I writing lower_bound() in Java again?

The second and the third time I find myself looking for a lower_bound() function according to generally accepted STL standard, I know that I'm not a Java-type developer. Java developers must have no need for these functions that I find very useful. A search for "java lower bound" or "java upper bound" does not yield the predictable result.

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)));
        }

    }