Serh.kry's blog

Ternary search vs bianry search
By Serh.kry, history, 8 years ago, In English

Can ternary search always be replaced by binary search with compare of f(x) and f(x + eps)?

I mean what is the point of cutting 1/3 when we can cut 1/2 and have error = eps?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

I don't really understand what you mean by f(x + eps),but check this blog :http://codeforces.me/blog/entry/11497

It might be useful.

→ Reply
»
8 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Going from f(x) to f(x + eps) or to f(x - eps) is neither binary nor ternary search. You don't get O(log) time in this case.

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

Binary*

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

Unimodal functions are functions with only one extreme point. Ternary search is, basically, a technique for finding the mode — e.g. the extreme point — of such a function. If the function is continuous and differentiable, which will probably be the case unless you work with discrete indices, the modified binary search basically searches for the x where f'(x) = 0, since (f(x + EPS) — f(x)) / EPS is a very good approximation to f'(x), for sufficiently small EPS. Because the derivative will always have a root at the extreme point, and there exists by definition of unimodality no other value that can have f'(x) = 0, the binary search you described is equivalent to ternary searching.

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

With infinitely precise calculation it should work.

the problem may be in that if you have x1 ≈ x2 = x1 + ε then f(x1) ≈ f(x2) and you may then go in wrong direction. It may be also the case for 1/3-division, but it will only happen when your range is too small, so that it almost won't affect the result

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

    I've had that happen once before, but to be honest, it's probably not something to worry about unless the function changes very violently or the required precision is very, very tight (as in 10^-12).

    → Reply