Sakalya's blog

By Sakalya, 8 years ago, In English,
Can anybody help me for implementing ternary search algorithm using C??
 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it -25 Vote: I do not like it
Why do you want to do that? So far I know(little) ternary search isn't really more efficient than binary search. :)
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    is not about efficiency... ternary search is sometimes necessity .... like if you are trying to find maximum or minimum point in U-shape graph, ternary search will work fine but binary search will not.

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

      why will binary search not work?

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

        How will you find maximum point with binary search?

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

          Using binary search on the f '(x) (derivative). I met that solution written by the one who didn't know ternary search.

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

          We can use binary search too.
          In each step of binary search, if f(mid-1) < f(mid) < f(mid+1), we are at the left side of answer, and if f(mid-1) > f(mid) > f(mid+1), we are at the right side of the answer. We are just on the answer when f(mid-1) <= f(mid) >= f(mid+1).

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            Actually it is ternary search after all.

»
8 years ago, # |
Rev. 4   Vote: I like it +5 Vote: I do not like it
if you want to find maximum of function
double l = ..., r = ..., EPS = ...; // input
while (r - l > EPS) {
   double m1 = l + (r - l) / 3,
      m2 = r - (r - l) / 3;
   if (f (m1) < f (m2)) // f - convex function
      l = m1;
   else
      r = m2;
}
f(r) - maximum of function
  • »
    »
    8 years ago, # ^ |
    Rev. 4   Vote: I like it +22 Vote: I do not like it

    Never do any searches (binary/ternary/etc) using r-l>EPS. This can result in infinite loop. You can read more about floating point numbers here.
    It's better to limit this loop by iterations. 300 iterations should be more than enough.


    P.S. f() can be not convex. Ternary search finds local minimum and maximum. So, it works on any function, that is monotonic both beyond and after some point. For example, it works on such function:


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

      But, on the other hand, the number of iterations becomes independent from the absolute values l​​and r, i.e. we are actually using the \ Rm iterations device ask the relative error . yeputons

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

    This will fail for Function F where F[1,2,3,4,5,6,7,8,9] = {1,2,2,2,2,2,2,3,1}.

    In other words i can not find maximima of array {1,2,2,2,2,2,2,3,1}

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

how does algo change when f(x) taken only intergers as input x.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Take zakharvoit's solution, but now round m1 downward and m2 upward. When you get m1 and m2 close enough (distance 2), just compute individually: f(m1), f(m1+1), and f(m2).

    (EDIT: Pressed Submit too early.)

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

    If you only want to search integers, it is easier and more efficient to just do binary search for the point when values start decreasing. See more here.

    You could do the same also with floats by computing numerical derivative of the function and binary searching when it goes to zero, but ternary search is more numerically stable. With integers numerical stability is typically not an issue.

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

    For strictly monotonic given algo will work. To make it work for such scenario we have tweak it.