Scala algorithm: Find k closest elements to a value in a sorted Array

Published

Algorithm goal

Find k closest elements to a value in a sorted Array. Assume no duplicates.

Test cases in Scala

``````assert(findClosest(arr = Array.empty, target = 5, k = 3) == Set.empty)
assert(
findClosest(arr = (1 to 10).toArray, target = 5, k = 3) == Set(4, 5, 6)
)
assert(
findClosest(arr = Array(1, 2, 3, 4, 6, 8, 9, 10), target = 5, k = 3) ==
Set(3, 4, 6)
)
``````

Algorithm in Scala

14 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!

Explanation

First, we need to find the closest element to the given value: Scala already provides us with a BinarySearch implementation which gives us a way to find an insertion point in an Array!

Then, based on this insertion point, we have a left range and a right range. (this is Â© from www.scala-algorithms.com)

Scala concepts & Hints

1. Def Inside Def

A great aspect of Scala is being able to declare functions inside functions, making it possible to reduce repetition.

``````def exampleDef(input: String): String = {
def surroundInputWith(char: Char): String = s"\$char\$input\$char"
surroundInputWith('-')
}

assert(exampleDef("test") == "-test-")
``````

It is also frequently used in combination with Tail Recursion.

2. Drop, Take, dropRight, takeRight

Scala's `drop` and `take` methods typically remove or select `n` items from a collection.

``````assert(List(1, 2, 3).drop(2) == List(3))

assert(List(1, 2, 3).take(2) == List(1, 2))

assert(List(1, 2, 3).dropRight(2) == List(1))

assert(List(1, 2, 3).takeRight(2) == List(2, 3))

assert((1 to 5).take(2) == (1 to 2))
``````
3. Lazy List

The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').

4. Ordering

In Scala, the 'Ordering' type is a 'type class' that contains methods to determine an ordering of specific types.

``````assert(List(3, 2, 1).sorted == List(1, 2, 3))

assert(List(3, 2, 1).sorted(Ordering[Int].reverse) == List(3, 2, 1))

assert(Ordering[Int].lt(1, 2))

assert(!Ordering[Int].lt(2, 1))
``````
5. Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

``````assert("Hello World".collect {
case character if Character.isUpperCase(character) => character.toLower
} == "hw")
``````
6. Range

The `(1 to n)` syntax produces a "Range" which is a representation of a sequence of numbers.

``````assert((1 to 5).toString == "Range 1 to 5")

assert((1 to 5).reverse.toString() == "Range 5 to 1 by -1")

assert((1 to 5).toList == List(1, 2, 3, 4, 5))
``````

Scala Algorithms: The most comprehensive library of algorithms in standard pure-functional Scala

Study our 92 Scala Algorithms: 6 fully free, 87 published & 5 upcoming

Fully unit-tested, with explanations and relevant concepts; new algorithms published about once a week.

Explore the 21 most useful Scala concepts

To save you going through various tutorials, we cherry-picked the most useful Scala concepts in a consistent form.

Register now (free)

Register with GitHub

How the algorithms look

1. A description/goal of the algorithm.
2. An explanation with both Scala and logical parts.
3. A proof or a derivation, where appropriate.
4. Links to Scala concepts used in this specific algorithm, also unit-tested.
5. An implementation in pure-functional immutable Scala, with efficiency in mind (for most algorithms, this is for paid subscribers only).
6. Unit tests, with a button to run them immediately in our in-browser IDE.