CODEWITHSUNDEEP
java
user459811
user459811

Reputation: 2894

Java: Find closest number in some collection

I have a static set of ordered numbers {1, 2, 4, 10, 14, 20, 21,24, 29, 30} that can be stored in any collections. If a new number is passed in, I need to be able to find the nearest greater number to the new number.

For example: If my static set of ordered number is {1, 2, 4, 10, 14, 20, 21,24, 29, 30}. The number passed in is 23, the closest greater number is 24.

I thought about storing the static numbers into an array. Looping the array and then trying to find the closest number but this solution is O(n). Is there a quicker way?

Upvotes: 1

Views: 1183

Answers (3)

Stephen C
Stephen C

Reputation: 718826

Assuming that the array of integers is sorted, then you can use Arrays.binarySearch(array, key).

The result of a binarySearch call is either the offset of the key in the array or the "insertion point"; i.e. the offset at which the key would need to be inserted. If you get an insertion point (expressed as a negative number), you can use that to identify the next largest or next smallest number in the array. (The exact meaning and representation of the "insertion point" is explained in the javadoc.)

The complexity of this procedure will be O(logN).

This will be faster than using Collections.binarySearch because the latter entails converting the int[] to an Integer[] before you can wrap it in a list. And if you started out with an Integer[], there is an alternative overload for Arrays.binarySearch that will work on any object array.

It will also be faster than creating a TreeSet from the input array. However, a TreeSet has the advantage that once you've created the set, updates will be cheaper ... compared to an array or arraylist-based representation. (But update is not part of the requirements as stated above.)

Upvotes: 3

user289086
user289086

Reputation:

Within Java 1.6, there's the NavigableSet interface. TreeSet and ConcurrentSkipListSet both implement this interface. Its a subinterface of SortedSet and intended to replace SortedSet.

So, you've got your collection in this NavigableSet now. You now have two methods - floor and ceiling which return the element that is lower than or greater respectively to the argument, or equal if there is one and null if there is no such element.

With this, you can do something along the lines of:

int closest(int arg) {
    Integer ceil = set.ceiling(arg);
    Integer floor = set.floor(arg);

    if(ceil == null) { return floor; }
    if(floor == null) { return ceil; }

    int cdiff = ceil - arg;
    int fdiff = arg - floor;

    if(cdiff < fdiff) { return ceil; }
    else { return floor; }
}

Realize that for small sized arrays, the difference in speed between this and other implementations is likely to be negligible.

If you are dealing with large sets of numbers, you may wish to look into implementing your own skip list (its a neat data structure) with a doubly linked bottom level. Then you can get to the spot where the value should be if it isn't, and easily go up or down the bottom level to get the next higher and lower number.

Upvotes: 3

doobop
doobop

Reputation: 4510

If you have the ordered list, you can just place it in a List and call Collections.binarySearch(list, valueToCheck)

If the return index is negative, then you'll need to convert it to the corresponding positive index and make sure the number is greater than the number passed in (should be converting it to a positive number, just watch out if it's greater then the last number in the list).

Upvotes: 0

Related Questions