I know the B.S and basic implementation of Ternary Search. But i don't know where to apply T.S ? When B.S fails... how do think that T.S would work?
For Eg: Problem : 439D - Devu and his Brother , Submission(T.S) : 6814294
Any help is Much Appreciated.
Thanks:)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
I'm not an expert to guide you, but I think this sheet might help: https://docs.google.com/spreadsheets/d/1iJZWP2nS_OB3kCTjq8L6TrJJ4o-5lhxDOyTaocSYc-k/edit#gid=84654839
This was created by Mr. Mostafa Saad. In the Topics section you'll be able to find practice problems on Ternary Search. Hope this helps :)
As far as I know, ternary search is used to find global maxima/ minima if a concave/ convex graph. suppose your search range is [l, r] and output function
f()is which gives value at a point. Now you need to find the point of minima (assumefover [l, r] forms a graph similar to x2). You can use ternary search in this case. Detailed Solution of same questionThanks harsh, great explanation in the given link.
But the problem of finding gobal max/min in concave/convex function can also be solved using binary search on the nature of graph(i.e. increasing or decreasing). Please correct me if I am wrong.
That's correct only if the domain is discrete, otherwise you should use ternary search.
If domain is continuous the answer must be till some precision value. Then the problem again become with discrete domain with higher precision.(Kind of fractional binary search)
As far as i know ternary search is used for unimodal functions(one maxima or one minima).For that derivative should increase first then decrease or vice-versa.which means d2F/dx2>=0 or d2F/dx2<=0 but not both.