omggg's blog

Binary Search Vs Ternary Search
By omggg, history, 4 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks harsh, great explanation in the given link.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's correct only if the domain is discrete, otherwise you should use ternary search.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply