CODEWITHSUNDEEP
java
Hobbyist
Hobbyist

Reputation: 16182

Most efficient way to find the nearest number in a list

I know what they say pre-optimization is the root of all evil however I'm more curious here as to what is the most efficient way to do this. Just a little more to the knowledge pool, you know?

Basically I have a collection of integers, like so:

final List<Integer> list = ImmutableList.of(1, 5, 10, 27, 57, 193);

Now I want to find the nearest number, rounded down. So for example I have the number 192. So the returned value from this list will be "57". Same applies if the number was 58. It just finds the next lowest number.

Currently I'm looping through the list starting from the end, using a for then returning the index of the list, which would be the number that I want. I'm just curious as to if there's a more efficient way to do this.

Upvotes: 1

Views: 1882

Answers (5)

Robert Otto
Robert Otto

Reputation: 1

use ConcurrentSkipListSet, and floor(value) to get the value less than or equal to the value specified. floor returns null if value argument is less than first value.

Upvotes: 0

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476534

Generic list

If nothing is known about the list, iterating over the list and memorizing the currently best solution is indeed the most efficient one.

If you however plan to do such query thousands of times, you might first sort the list.

Sorted list

If the list is sorted you can use the binarySearch(List<? extends Comparable<? super T>> list, T key) method. This method returns the insertion point of a new element. In case the element exists, a positive index of that element is returned. Otherwise the bitwise negation of the insertion index is returned.

You can then call it with:

//only to be used if list is sorted (a priori)
public int closestValue (List<Integer> list, int value) {
    int index = Collections.binarySearch(list,value);
    if(index < 0) {
        index = ~index-1;
    }
    return list.get(index);
}

jdoodle demo.

The method will throw an IndexOutOfBoundsException in case there is no such element.

Binary search can be done in O(log n), but only - as said before - if the list is sorted.

Upvotes: 5

user1283559
user1283559

Reputation: 49

Create a HashMap the size of your maximum value, then fill the map with key pair of the expected result. i.e map.put(6,5);map.put(7,5) and so on.

After that getting the correct value will be in O(1).

Of course the creation of the Map will take more time and recourse but over a infinite amount of time this will yield the fastest result.

Upvotes: -2

rrohit
rrohit

Reputation: 31

If the list is sorted , then you can do the Binary Search on the list and You can get your no in Log(n).

Upvotes: 2

Bitcoin M
Bitcoin M

Reputation: 1206

You can sort the list and then use a binary-search like method to find the nearest number.

Upvotes: 1

Related Questions