Блог пользователя Bobek

Binary search vs ternary search
Автор Bobek, история, 7 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

        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.

        → Ответить