how to find/filter the array element with the smallest positive difference

Question

Using Swift, I am trying to workout a complex array filter or sort and I am stuck. My array of integers can contain between 1 and 7 elements. Given a certain integer value (say X) which is not in the array, I would like to find the array element that gives the smallest difference between itself and X.

Solution 1

In Swift 2 you can do it as a "one-liner" with functional-style programming:

let numbers = [ 1, 3, 7, 11]
let x = 6

let closest = numbers.enumerate().minElement( { abs($0.1 - x) < abs($1.1 - x)} )!

print(closest.element) // 7 = the closest element
print(closest.index)   // 2 = index of the closest element

enumerate() iterates over all array elements together with the corresponding index, and minElement() returns the "smallest" (index, element) pair with respect to the closure. The closure compares the absolute values of the difference of two elements to x.

(It is assumed here that the array is not empty, so that minElement() does not return nil.)

Note that this is probably not the fastest solution for large arrays, because the absolute differences are computed twice for (almost) all array elements. But for small arrays this should not matter.

Swift 3:

let numbers = [ 1, 3, 7, 11]
let x = 6
let closest = numbers.enumerated().min( by: { abs($0.1 - x) < abs($1.1 - x) } )!
print(closest.element) // 7
print(closest.offset) // 2

The Swift 1.2 version can be found in the edit history.

Solution 2

Swift 4.2

Not exactly what the OP is asking, but you can use the first(where:) and firstIndex(where:) array methods on a sorted array to get the first value greater than x:

let numbers = [1, 3, 7, 11]

let x = 6
let index = numbers.firstIndex(where: { $0 >= x })!
let result = numbers.first(where: { $0 >= x })!

print(index, result) // 2 7

Solution 3

Loop through the values in your array, calculate the abs() difference, compare it to a running 'currentSmallestDifference' variable, if the current difference is smaller than that then overwrite it with the new value, at the same time keep a record of the array index...

int currentSmallestDifference = int.max(); //largest value defined by the int type, this way the first difference in the loop will never be larger than this 
int index = -1;   
for(int i = 0, i < array.size(), i++){
    if( abs(array(i) - X) < currentSmallestDifference){
        currentSmallestDifference = abs(array(i) - X);
        index = i;
    }
}

This solves it in O(n).

But if the array was already sorted (O(nlog(n)), you could then do a O(log(n)) binary search for X in the array and find the closest value to it. No need to use abs() at all in that case... just comparisons

But for array sizes 1 to 7, algorithmic complexity isn't really a factor.

In fact for array size 1, the question isn't even a factor (?!?)

Update>> Just realised the title said smallest positive difference.. So just ditch all the abs() stuff and make sure (array(i) - X) is in the correct sign/direction.

Solution 4

Another alternative would be to use the reduce method

let numbers = [1, 3, 7, 11]
let x = 11

let result = numbers.reduce(numbers.first!) { abs($1 - x) < abs($0 - x) ? $1 : $0 }

If you want to avoid repeated calculation of the absolutes, you could first map every array element to it's absolute difference from the input number and then find the minimum.

let numbers = [1, 3, 7, 11]
let x = 11

if let (index, _) = numbers.map({ abs($0 - x) }).enumerate().minElement({ $0.1 < $1.1 }) {
    let result = numbers[index]
}

Solution 5

Wrapped this into an extension:

extension Sequence where Iterator.Element: SignedNumeric & Comparable {

    /// Finds the nearest (offset, element) to the specified element.
    func nearestOffsetAndElement(to toElement: Iterator.Element) -> (offset: Int, element: Iterator.Element) {

        guard let nearest = enumerated().min( by: {
            let left = $0.1 - toElement
            let right = $1.1 - toElement
            return abs(left) <= abs(right)
        } ) else {
            return (offset: 0, element: toElement)
        }

        return nearest
    }

    func nearestElement(to element: Iterator.Element) -> Iterator.Element {
        return nearestOffsetAndElement(to: element).element
    }

    func indexOfNearestElement(to element: Iterator.Element) -> Int {
        return nearestOffsetAndElement(to: element).offset
    }

}

View more solutions

Comments

[hennes]

I think it's better to make currentSmallestDifference an optional than to use 999999999 or some other constant.

[Martin R]

... or initialize with Int.max.

[Lamar Latrell]

Int.max is what I had in mind, I just didn't know such a thing would be accepted in the parlance of psuedocode...

[Martin R]

@LamarLatrell: I really meant Int.max, which is not pseudocode but real working Swift code. It returns the largest possible value for the Int type. Your int.max() does not compile.

[Lamar Latrell]

oooh, ok - so hrrrrm, I see the tag in the original question now :)

[chronos]

Sorry for not replying earlier. Actually my elements don't exceed 7 but I am still using Swift 1.2. I would really appreciate it if you could include a Swift 1.2 functional-style solution.

[Martin R]

@chronos: Do you need the closest value only or do you need the index as well?

[chronos]

The index is the main thing I need.

[Martin R]

@chronos: See update. Note that Xcode 7 is final now, so spending too much time on Swift 1.2 code is perhaps not worth the hassle.

[chronos]

Thanks, just updating to Xcode 7. This might not be exactly related to the question but I've watched the WWDC 2015 video on What's New In Swift and it basically scratches the surface. Do you know of any resource that gives in-depth info mainly on new functions in Swift 2?

[craft]

This answer was useful for me (thanks!), but downvoting because it's actually not the answer to the question. They asked for the closest number, not the next one in the series. Proof for that is if x = 4, then result == 7 which is not the closest number

[David]

How would we achieve this if we wanted to compare to a property of the array element?