Given a number, how to find a closest number in a series of floating point data

Question

I came across this question while looking for Amazon interview questions and wanted to ask.

Given a number, how can you find the closest number in a series of floating point data?

If everything is integer , answer is substracting the number from every number in the array, then look for the element with minimum absolute value in the array.

But when it comes to floating points, it should be highly nontirival.

Ani ideas?? Thanks.

Answer 1

The problem with floats is rounding errors. However, comparison of floats is not subject to rounding errors: therefore, you can correctly find the number just bigger and just smaller than x in linear time:

sm = -inf;
bg = inf;
for(i from 0 to n)
  if(arr[i] > x && arr[i] < bg)
    bg = arr[i];
  if(arr[i] < x && arr[i] > sm)
    sm = arr[i];

Now you only need to determine which of these two numbers is closer to x. Since bg is bigger and sm is smaller, the only time you can have rounding error is when bg >> x or x >> sm; in either of these cases, it will only increase the magnitude of the rounded difference.

(If the magnitudes are the same, for instance if x=1 and arr=[1e100, -1e100], you can know that x is closer to the value with the same sign as itself.)