cum00's blog

Everyone Writes Continuous Ternary Search Suboptimally (Even tourist)
By cum00, history, 2 years ago, In English

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!".

  • Vote: I like it
  • -67
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

based

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    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.

    → Reply
»
2 years ago, # |
← Rev. 4   Vote: I like it +20 Vote: I do not like it

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.

→ Reply
»
2 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Can you point us to a problem where golden section works and naive ternary search doesn't? Thanks

→ Reply
»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
2 years ago, # |
  Vote: I like it +59 Vote: I do not like it

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.

    double lm = l + (r - l) / 2.1;
    double rm = r - (r - l) / 2.1;

This way of writing forces it to find answer much faster (perhaps making it a little less stable).

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But it is still worse than golden-section, because $$$\varphi^2 > 2$$$.

    → Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

"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.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply