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

/**
*  Testing equalities and duplicates.
*/
// testing equality and duplicates. eg: consider input like: 1, 2, 2, 5
if (arr[mid] == x || arr[mid + 1] == x) {
return x;
}

/**
*  Testing when element is in the range of array elements.
*/
// input x in range of array elements.
if (arr[mid] < x && arr[mid + 1] > 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 {
/**
*/
public static int greatestIndexNotExceeding(int[] data, int limit) {
if (data.length < 1) {
return -1;
}
return greatestIndexNotExceeding(data, limit, 0, data.length - 1);
}

private static int greatestIndexNotExceeding(int[] data, int limit, int lb, int ub) {
final int mid = (lb + ub) / 2;

// Need to go lower but can't
if (mid == lb && data[mid] > limit) {
return -1;
}

// Found a candidate, and can't go higher
if (data[mid] <= limit && (mid == ub || data[mid + 1] > 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.

That is not a class: it is a collection of functions. A class has attributes (instance variables) and behaviours (methods that perform operations on the data):

A class is a software element describing an abstract data type and its partial or total implementation. An abstract data type is a set of objects defined by the list of operations, or features, applicable to these objects, and the properties of these operations.

~ Bertrand Meyer, Object-Oriented Software Construction, 2nd Edition, p.23.

Consider:

/**
* Allows clients to determine the first value that matches
* a list of values, based on a particular comparator.
*/
public class Determinator {
private int[] list = new int[0];
private Comparator comparator;

public Determinator( int[] list ) {
this( list, new LessThanComparator() );
}

public Determinator( int[] list, Comparator comparator ) {
setList( list );
setComparator( comparator );
}

private void setList( int[] list ) {
if( list != null ) {
this.list = list;
}
}

private void setComparator( Comparator comparator ) {
// Same as setList...
}

/**
* Finds the first value in the list that has the relationship
* to x as denoted by the comparator option.
*
* @param x The value to compare against the list of values.
* @throws InvalidParameterException There was no valid value to return.
*/
public int findValue( int x ) throws InvalidParameterException {
}

public boolean isWithinBoundary( ... ) {
}

public boolean isDuplicate( ... ) {
}

public boolean isInRange( ... ) {
}
}


Note:

• All assertions and tests for null values are no longer necessary.
• The interface (i.e., method definitions) for how the class works can be written independently of the methods themselves.
• Using a Comparator object makes the code more generic, as it can perform any number of comparisons beyond less-than-or-equal-to.
• The logic has been separated into smaller, more manageable methods.
• No null values are returned: an exception is thrown when a suitable value is not found.
• Please explain the downvotes so that we all can learn. Commented Oct 21, 2013 at 17:33
• No idea what the downvote was for, since this is a useful answer. +1. Some critiques, though: 1) if you use Comparator, you should explicitly assign the generic type <T>; 2) a constructor with less arguments should always refer to a constructor with more arguments, not the other way around; 3) throwing an Exception if no value is found is a bad approach - Exceptions should be used for errors, not for control flow; 4) Saying "That is not a class" may be misleading to new Java developers. It is a class, just one that only has static methods and would be useless to instantiate. Commented Oct 21, 2013 at 17:40
• Upon further thought, the Exception throwing might not be that bad, depending on the use of this API and how "low-level" you intend it to be. It's a serious design consideration, though. Commented Oct 21, 2013 at 17:43
• Haha, I'd never read the "Hoare's billion dollar mistake" quote. Very nice. Commented Oct 21, 2013 at 18:07
• 1) Agreed. 2) Fixed. 3) Disagree (see Hoare's billion dollar mistake). 4) Disagree; see update. Commented Oct 21, 2013 at 18:13