### omggg's blog

By omggg, history, 4 years ago,

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:)

• +8

 » 4 years ago, # |   0 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=84654839This was created by Mr. Mostafa Saad. In the Topics section you'll be able to find practice problems on Ternary Search. Hope this helps :)
 » 4 years ago, # | ← Rev. 3 →   0 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 (assume f over [l, r] forms a graph similar to x2). You can use ternary search in this case. Detailed Solution of same question
•  » » 4 years ago, # ^ |   0 Thanks harsh, great explanation in the given link.
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 That's correct only if the domain is discrete, otherwise you should use ternary search.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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)
 » 4 years ago, # |   0 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.