Finding the closest number in a random set

Question

Say I got a set of 10 random numbers between 0 and 100.

An operator gives me also a random number between 0 and 100. Then I got to find the number in the set that is the closest from the number the operator gave me.

example

set = {1,10,34,39,69,89,94,96,98,100}

operator number = 45

return = 39

And how do translate this into code? (javascript or something)

Answer 1

How about this:

1) Put the set into a binary tree.
2) Insert the operator number into the tree
3) Return the Operators parent

Answer 2

if set is ordered, do a binary search to find the value, (or the 2 values) that are closest. Then distinguish which of 2 is closest by ... subtracting?

If set is not ordered, just iterate through the set, (Sorting it would itself take more than one pass), and for each member, check to see if the difference is smaller than the smallest difference you have seen so far, and if it is, record it as the new smallest difference, and that number as the new candidate answer. .

  public int FindClosest(int targetVal, int[] set)
  {
      int dif = 100, cand = 0;
      foreach(int x in set)
          if (Math.Abs(x-targetVal) < dif)
          {
              dif = Math.Abs(x-targetVal);
              cand = x;
          }
      return cand;
  }

Answer 3

• given an array called input, create another array of the same size
• each element of this new array is the Math.abs(input[i] - operatorNumber)
• select the index of the mininum element (let's call it k)
• your answer is input[k]

NB

• sorting is not needed
• you can do it without the extra array

Sample implementation in JavaScript

function closestTo(number, set) {
    var closest = set[0];
    var prev = Math.abs(set[0] - number);

    for (var i = 1; i < set.length; i++) {
        var diff = Math.abs(set[i] - number);

        if (diff < prev) {
            prev = diff;
            closest = set[i];
        }
    }

    return closest;
}

Answer 4

Someone tagged this question Mathematica, so here's a Mathematica answer:

set = {1,10,34,39,69,89,94,96,98,100};

opno = 45;

set[[Flatten[
  Position[set - opno, i_ /; Abs[i] == Min[Abs[set - opno]]]]]]

It works when there are multiple elements of set equally distant from the operator number.

Answer 5

1. order the set
2. binary search for the input
3. if you end up between two elements, check the difference, and return the one with the smallest difference.

Answer 6

python example:

#!/usr/bin/env python
import random
from operator import itemgetter

sample = random.sample(range(100), 10)
pivot = random.randint(0, 100)

print 'sample: ', sample
print 'pivot:', pivot
print 'closest:', sample[
    sorted(
        map(lambda i, e: (i, abs(e - pivot)), range(10), sample), 
        key=itemgetter(1)
    )[1][0]]

# sample:  [61, 2, 3, 85, 15, 18, 19, 8, 66, 4]
# pivot: 51
# closest: 66