how to find/filter the array element with the smal

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.

Answer 1

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.

Answer 2

Here is a method that does a single loop that calculates the closest positive value. Not a one-liner. But still effective

let values = [1, 4, 9, 3, 8, 2, 11]
let x = 8

func closestPositiveValue(from array: [Int], value: Int) -> (Int, Int) { // -> (value, difference)
  var (val, dif): (Int?, Int?) = (nil, nil)
  for index in 0..<array.count {
    if x <= array[index] {
      var difference = x - array[index]
      if difference < 0 {
        difference = array[index] - x
      }
      if val == nil { // nil check for initial loop
        (val, dif) = (array[index], difference)
      } else {
        if difference < dif! {
          (val, dif) = (array[index], difference)
        }
      }
    }
  }
  return (val ?? 0, dif ?? 0) // defaults to first item in array if there is no closest positive number
}
print(closestPositiveValue(from: values, value: x)) // prints (8, 0)

Answer 3

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
    }

}

Answer 4

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.

Answer 5

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]
}

Answer 6

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