Angesichts einer Nummer, wie man eine nächste Nummer in einer Reihe von Gleitkommadaten

Question

finden Ich stieß auf diese Frage bei der Suche nach Amazon Interview Fragen und wollte fragen.

Wie können Sie anhand einer Zahl die nächste Zahl in einer Reihe von Fließkommadaten finden?

Wenn alles eine Ganzzahl ist, subtrahiert antvice die Zahl von jeder Zahl im Array und sucht dann im Array nach dem Element mit dem kleinsten absoluten Wert.

Aber wenn es um Gleitpunkte geht, sollte es in hohem Grade nicht fortlaufend sein.

Ani Ideen ?? Vielen Dank.

Answer 1

Das Problem mit Floats ist Rundungsfehler. Bei einem Vergleich des Schwimmer ist auf Rundungsfehler nicht Gegenstand: Daher können Sie richtig die Zahl finden nur größer und nur kleiner als x in linearer Zeit:

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

Jetzt brauchen Sie nur, welche diese beiden Zahlen zu bestimmen, näher an x. Da bg ist größer und sm ist kleiner, die einzige Zeit, die Sie Rundungsfehler haben können, ist, wenn bg >> x oder x >> sm; in jedem dieser Fälle erhöht es nur die Größe der gerundeten Differenz.

(Wenn die Größen gleich sind, zum Beispiel, wenn x=1 und arr=[1e100, -1e100], können Sie wissen, dass x mit dem gleichen Vorzeichen wie sich der Wert näher ist.)