how to find/filter the array element with the smallest positive difference
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]
}
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.
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
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.