Ich habe eine Funktion, die ein Double zurückgibt. Die folgende Code-Liste ist ein Beispiel, das ich zum Testen verwende, aber die echte Funktion wird aus einer Analyse eines Datensatzes gezogen.
public double f(double x)
{
return (100000 - x) / 15000;
}
Es kann angenommen werden, dass ein höherer Wert von x immer einen niedrigeren Wert zurückgibt, so dass sich x möglicherweise dem Wert von 0 nähert, aber möglicherweise immer bei 0 bleiben kann.
Werte von x sind immer positiv.
Ich würde gerne den niedrigsten Wert von findenf (x) das ist> = bis 7, wenn es mit einem gegebenen minimalen und maximalen Wert geliefert wird (Genauigkeit ist nur 0,001). Im obigen Beispiel verwende ich 100000 als maximalen Wert und 1 als Minimum.
Ist das ein guter Kandidat für eine binäre Suche oder gibt es eine bessere Alternative?
Antworten:
2 für die Antwort № 1Ja und nein.
Wenn die monotone Funktion nicht zu einem endlichen Wert konvergiert - als yes, könnten Sie die binäre Suche wie folgt verwenden:
i <- 1
while (f(i) > target):
i <- i*2
binary search for target in the range `[2^(i-1),2^i]` for best candidate.
Die Komplexität des Obigen ist O(log(i)) - woher i ist der Index des nächsten Elements.
Beachten Sie jedoch, dass alle Wetten deaktiviert sind, wenn die Funktion auf einen konstanten Wert konvergiert.
Zum Beispiel wird es Ihnen nicht helfen, den nächsten Wert zu finden -1 für die Funktion f(i) = 1/i. In diesem Fall befindet sich der Algorithmus in einer Endlosschleife.