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

Автор Bobek, история, 3 месяца назад, По-английски,

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
  • Проголосовать: не нравится  

»
3 месяца назад, # |
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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        3 месяца назад, # ^ |
        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.