CODEWITHSUNDEEP
kotlin
Johann
Johann

Reputation: 29867

Finding the nearest/closest value in a collection but not exceeding it

I have a collection and want to return the nearest value to some fixed value but not exceed the fixed value. For example, if my collection looks like this:

val numbers = mutableListOf(23, 12, 64, 47, 36, 55)

and I have a target fixed value of 35, the value returned from the collection would be 23. Here are some other examples:

Target -> Returned
29 -> 23
5 -> null (there is no value less than 12, so null is returned)
70 -> 64

Is there some Collection function that I can use that would provide the expected result? Note: The list of numbers is not sorted. In the real app, these are not numbers but objects that do contain an integer property, but I could just as well sort the collection first on that value if that would help in the solution.

Upvotes: 4

Views: 2729

Answers (4)

sidgate
sidgate

Reputation: 15244

You can use fold function to hold the closest value in an accumulator. For instance,

val numbers = mutableListOf(23, 12, 64, 47, 36, 55)

val target = 35

val answer = numbers.fold(null){acc: Int?, num ->
    if(num <= target && (acc == null || num > acc)) num
    else acc
}

In case you want to break the loop if the target matches one of the values in the list you can have the following

val numbers = mutableListOf(23, 12, 64, 47, 36, 55)
val target = 35

fun MutableList<Int>.findClosest(input: Int) = fold(null) { acc: Int?, num ->
    val closest = if (num <= input && (acc == null || num > acc)) num else acc
    if (closest == input) return@findClosest closest else return@fold closest
}

val answer = numbers.findClosest(target)

The return keyword in the inner function will return from findClosest function as soon as the target matches a particular value

Upvotes: 6

Tenfour04
Tenfour04

Reputation: 93629

I would use

numbers.asSequence().filter { it <= target }.maxOfOrNull()

I think it's self-explanatory.

Upvotes: 1

Sweeper
Sweeper

Reputation: 271625

You should use minByOrNull. You want to find the number with the minimum difference from target. But before doing that, you should filter out those that are more than target.

numbers.filter { it <= target }.minByOrNull { target - it }

This will loop through numbers twice. If you don't like that, you can add asSequence() before .filter.

Upvotes: 2

mightyWOZ
mightyWOZ

Reputation: 8335

I don't know of any function from the library that would solve it, but you can define your own extension as

fun <T: Comparable<T>> Iterable<T>.findPredecessor(value: T): T?{
        var currentCandidate: T? = null
        this.filter { it < value }. forEach {
            currentCandidate = when {
                currentCandidate == null -> it
                currentCandidate!! < it  -> it
                else -> currentCandidate
            }
        }
        return currentCandidate
    }

Also if this is a one-two time operation then you are ok with iteration, otherwise you should sort the input and then use a modified binary search.

Upvotes: 1

Related Questions