Can anybody help me for implementing ternary search algorithm using C??

Codeforces and Polygon may be unavailable between Aug. 17, 19:00 (UTC) to Aug. 17, 22:00 (UTC) due to planned power outages.
×

# | User | Rating |
---|---|---|

1 | tourist | 3851 |

2 | jiangly | 3634 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | ksun48 | 3493 |

6 | djq_cpp | 3486 |

7 | maroonrk | 3471 |

8 | MiracleFaFa | 3466 |

9 | Radewoosh | 3442 |

10 | Petr | 3426 |

# | User | Contrib. |
---|---|---|

1 | -is-this-fft- | 183 |

2 | awoo | 181 |

3 | YouKn0wWho | 177 |

4 | Um_nik | 175 |

5 | dario2994 | 172 |

6 | Monogon | 170 |

6 | adamant | 170 |

8 | maroonrk | 169 |

9 | errorgorn | 166 |

10 | antontrygubO_o | 165 |

Can anybody help me for implementing ternary search algorithm using C??

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/17/2022 20:17:39 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

why will binary search not work?

How will you find maximum point with binary search?

Using binary search on the

f'(x) (derivative). I met that solution written by the one who didn't know ternary search.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).

Actually it is ternary search after all.

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:

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

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}

That's not

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

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

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.

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