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

Автор Bobek, история, 10 месяцев назад, ,

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
•

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