CODEWITHSUNDEEP
algorithmmathset
Andy Jacobs
Andy Jacobs

Reputation: 15245

Finding the closest number in a random set

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)

Upvotes: 4

Views: 8900

Answers (6)

High Performance Mark
High Performance Mark

Reputation: 78364

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.

Upvotes: 1

dfa
dfa

Reputation: 116412

  • 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;
}

Upvotes: 6

miku
miku

Reputation: 188164

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

Upvotes: 0

Charles Bretana
Charles Bretana

Reputation: 146567

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

Upvotes: 8

GSto
GSto

Reputation: 42380

  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.

Upvotes: 1

tinkertime
tinkertime

Reputation: 3042

How about this:

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

Upvotes: 1

Related Questions