Dato un numero, come trovare un numero più vicino in una serie di dati in virgola mobile

Question

Mi sono imbattuto in questa domanda mentre cercavo le domande di un'intervista Amazon e volevo chiedere.

Dato un numero, come si può trovare il numero più vicino in una serie di dati in virgola mobile?

Se tutto è intero, la risposta sta sottraendo il numero da ogni numero nell'array, quindi cerca l'elemento con il valore assoluto minimo nell'array.

Ma quando si tratta di punti in virgola mobile, dovrebbe essere altamente nontivalente.

Ani idee ?? Grazie.

Answer 1

Il problema con i float è l'arrotondamento degli errori. Tuttavia, il confronto di carri non è soggetto ad errori di arrotondamento: di conseguenza, si può correttamente trovare il numero appena più grande e appena più piccolo di x in tempo lineare:

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

Ora avete solo bisogno di determinare quale di questi due numeri è più vicino a x. Poiché bg è più grande e sm è più piccolo, l'unica volta che si può avere un errore di arrotondamento è quando bg >> x o x >> sm; in entrambi i casi, aumenterà solo la grandezza della differenza arrotondata.

(Se le grandezze sono gli stessi, per esempio se x=1 e arr=[1e100, -1e100], si può sapere che x è più vicino al valore con lo stesso segno di sé.)