Finding greatest value in array smaller than x

Code review requested to make this code simpler, cleaner, and better. Input array is sorted.

This program finds the greatest number smaller than x. So, in an array [10 20 30 40] and x = 25, the output should be 20.

public class GreatestValueLesserThanEqualToX {

    public static Integer findGreatestValueLesserThanOrEqualToX (int[] arr, int x) {
        if (arr == null) {
            throw new NullPointerException(" The input array is null. ");
        }
        if (arr.length >= 1) {
            return findGreatestValueLesserThanOrEqualToX (arr, x, 0, arr.length - 1);
        } else {
            return null;  // note the difference wrt greatest value lesser than X.
        }
    }

    private static Integer findGreatestValueLesserThanOrEqualToX (int[] arr, int x, int lb, int ub) {

        assert arr != null;

        final int mid = (lb + ub) / 2;

        /**
         *  Testing boundaries.
         */
        // testing lower boundary.
        if (mid == 0) {
            if (arr[mid] > x) {
                return null;
            }

            // single element array with value lesser than input value.
            if (arr.length == 1) {
                return arr[0];
            }
        }

        //testing higher boundary.
        if (lb == (arr.length - 1) && arr[mid]  x) {
             return arr[mid]; // note the difference wrt greatest value lesser than X.
         }

         if (arr[mid] < x) {
             return findGreatestValueLesserThanOrEqualToX (arr, x, mid + 1, ub);
         } else {
             return findGreatestValueLesserThanOrEqualToX (arr, x, lb, mid);
         }
     }
}

Interface Design

The class could be better named. (As @DaveJarvis points out, it's more of a namespace than a class, but I'm OK with a design that is not pure OOP.) I suggest BinarySearcher: it describes what it can do, without repeating the name of the function, and still leaves it open for you to add a findSmallestValueGreaterThanOrEqualToX() function later.

Returning an Integer is weird, especially since the inputs are unboxed ints. I know, you want to be able to return null if no suitable element is found. I have another suggestion: return the index of the element found rather than the element itself; if no suitable element exists then return -1. That behaviour is reminiscent of String.indexOf(), which all Java programmers should be familiar with. Knowing the index, the caller can easily retrieve the element from the array.

We could also shorten the function name a bit. I suggest that the method signature should be

/**
 * Given a sorted array and a limit, finds the rightmost element
 * whose value does not exceed the limit.
 *
 * @param data An array sorted in ascending order
 * @param limit The maximum value to look for
 * @return The index of the last element in data whose value is less
 *         than or equal to limit.  If no such element exists, returns -1.
 */
public static int greatestIndexNotExceeding(int[] data, int limit)

Search Logic

There is no reason for your helper function to consult arr.length. The helper function's job is to look between indices lb and ub. The caller will vouch for the validity of those bounds. What happens beyond that range is none of the helper function's business.

You have seven cases, which is way too many. You should only need four:

• No suitable element

• Found the result

• Consider the upper half of the range

• Consider the lower half of the range

Null-Handling

There's no need to throw new NullPointerException() explicitly. The very next line will raise a NullPointerException naturally when it tries to access arr.length. The arr != null assertion is similarly pointless.

When might it be beneficial to check for null explicitly? When a constructor or a setter method accepts an argument and stores it for future use, but does not try to use it immediately. In those cases, it can be hard to track down later how an instance or class variable came to be null.

Proposed Solution

public class BinarySearcher {
    /**
     * Insert JavaDoc here…
     */
    public static int greatestIndexNotExceeding(int[] data, int limit) {
        if (data.length  limit) {
            return -1;
        }

        // Found a candidate, and can't go higher
        if (data[mid]  limit)) {
            return mid;
        }

        if (data[mid] <= limit) {
            // Consider upper half
            return greatestIndexNotExceeding(data, limit, mid + 1, ub);
        } else {
            // Consider lower half
            return greatestIndexNotExceeding(data, limit, lb, mid);
        }
    }
}

It should be possible to restructure the code to reduce the number of comparisons between data[mid] and limit, but I think it's more readable this way.

StackExchange Code Review Q#33009, answer score: 2