Biorąc pod uwagę liczbę, jak znaleźć najbliższy numer w serii danych zmiennoprzecinkowych

Question

Natknąłem się na to pytanie, szukając pytań do wywiadu z Amazon i chciałem zapytać.

Podając liczbę, jak znaleźć najbliższy numer w serii danych zmiennoprzecinkowych?

Jeśli wszystko jest liczbą całkowitą, odpowiedź odejmuje liczbę od każdej liczby w tablicy, a następnie poszukaj elementu z minimalną wartością bezwzględną w tablicy.

Ale jeśli chodzi o punkty zmiennoprzecinkowe, to powinno być wysoce nieprzywijające.

Pomysły Ani? Dzięki.

Answer 1

Problem z pływakiem to błędy zaokrąglania. Jednak porównanie z pływaków nie podlega błędów zaokrągleń: w związku z tym, można właściwie znaleźć numer po prostu większy i tak mniejszy niż x w czasie liniowym:

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

Teraz tylko trzeba określić, które z tych dwóch liczb jest bliżej do x. Ponieważ bg jest większy, a sm jest mniejszy, jedynym błędem zaokrąglania jest bg >> x lub x >> sm; w każdym z tych przypadków zwiększy tylko wielkość zaokrąglonej różnicy.

(Jeśli wielkości są takie same, na przykład jeśli x=1 i arr=[1e100, -1e100], można wiedzieć, że x jest bliższa wartości z tego samego znaku jak sama).