When it comes to writing a ternary search, what you usually do is this:
repeat 30/60/100/200 times {
double lm = l + (r - l) / 3;
double rm = r - (r - l) / 3;
if (f(lm) < f(rm))
r = rm;
else
l = lm;
}
Sources (notice the authors): 154861075 154863973
I recommend everyone who still writes like this to read this article . It will improve your ability to fit nested ternary searches. Also, I hope I don't need to explain why it is strictly better than the shown code.
Please, refrain from writing in the comments "but still their code works and is accepted!!1!".
based
If you want to say something, just say, do not assume that everybody can read your mind.
Do you mean that the correct algo should iterate while the difference is more than a constant? Well, I have bad news for you. One day your solution would fail with a time limit just because such checks will always pass due to a lack of enough precision in float/double.
As I know, main idea of golden-section search is not about termination condition, but about total amount of function calculations.
Due to golden-section ratio properties on each step you need calculate function only for one new point, because second point was calculated on some previous step.
Thank you for your blog.
I remember that someone told me this way is a slow way to solve ternary search.
However, if the upper and lower bounds are integers, your way is not so proper. see this one(Chinese). PinkieRabbit said that.
Forgive my poor English, thanks very much.
UPD: You added "continuous". Your way is really faster, however, maybe it is difficult to implement it.
Can you point us to a problem where golden section works and naive ternary search doesn't? Thanks
Maybe some interactive problems?(forgive I have not seen)
Not exactly what you're asking for but there are some JOI spring camp and BOI interactive problems which required you to do golden ratio search instead of binary search.
BOI 2018 worms was the problem. But the issue was that they counted the number of queries.
There's a problem like that in codechef. I'll look for it after the contest.
3 months late but:
https://www.codechef.com/submit/GUESSG?tab=statement
there's also this problem https://mirror.codeforces.com/contest/1746/problem/E2 :)
Not exactly golden ratio search, but it's optimizing some search
There are reasons why strong competitors use a standard ternary search. It's simple and it works.
Golden ratio ternary search is more tricky to implement. You need to remember and pass some value. It's more difficult to analyze the precision error. Integer-based version (ternary search in a sequence) is ugly because of rounding.
You can share your implementation though.
Thanks for the opinion. Unfortunately, everyone missed the point that I fit 4 searches and had 0 chance to fuckup while coding circles intersection.
155828289
Ternary search does not use the idea of dividing into three equal parts. You can make it almost binary by keeping the middle part small. After all, you just need to look at the value of the derivative at the midpoint.
This way of writing forces it to find answer much faster (perhaps making it a little less stable).
But it is still worse than golden-section, because $$$\varphi^2 > 2$$$.
"but still their code works and is accepted!!1!" or in a normal tone
If something can be done faster it doesn't mean it must be. We usually try to write the most straightforward code that will work for given limitations. In the problem you mentioned time limit is not an issue. For me personally golden ternary search is messy, so I avoid it unless I can't get accepted otherwise.
Thanks for the opinion. Unfortunately, everyone missed the point that I fit 4 searches and had 0 chance to fuckup while coding circles intersection.
Yeah, writing circles intersection is the most straightforward way instead of fitting 4 searches.