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

user_753632 0
Viewed 544

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.

kotlin
4 Answers

You can use fold function to hold the closest value in an accumalator. 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 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

user_9779190

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.

user_44130980

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.

user_51335850

I would use

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

I think it's self-explanatory.

user_5067960
Related