Bobek's blog

Binary search vs ternary search
By Bobek, history, 7 years ago, In English

I read some articles about ternary search and it seems that it's very similar to binary search, but we divide interval on three rarther than two parts. Is there any problem that can be solved using ternary search and can't be solved using (or at least much harder) binary search ? When should I use ternary search over binary search ?

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Ternary search is used when you need to find the extreme value of a unimodal function, for example -x^2+3, which has is strictly increasing, then it has a maximum at x=0, then it is strictly decreasing. You can read about this application here.

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

    I read that, but it doesn't help. In binary search we also look for minimum/maximum, so I guess it also applies to unimodal functions

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

      It can't, because in a binary search needs a function that is monotonic. For example i'll use -x^2 +3. Let's say that binary search has found for some x that value is 2. You can't determine whether you should look for x that is larger or smaller than your current x because x can be both 1 and -1, and the maximum is achieved when x is 0.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it

        Actually you can also use binary search for an unimodal function.

        For some positive epsilon ε, we look at the values f(x) and f(x + ε). If f(x) < f(x + ε), then x is left of the apex (or close enough to the apex). Otherwise, x is right of the apex. However this can't always be used due to precision issues.

        → Reply