Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Captain_Knuckles's blog

By Captain_Knuckles, history, 6 days ago, In English,

Hi codeforces

Today i will talk about special case in Ternary search

You know when we use Ternary search it's done on a parabola to find its peak

This is a simple code to find the peak of a parabola where the peak is facing down :

L = range_beginning, R = range_ending;

while(R > L) {
    x = (L+R)/2; 
    if( f(x+1) < f(x) )
        L = x+1;
    else
        R = x;
}

But in this special case i need to find the peak of a parabola that has constant value in some ranges as shown on the photo below :

You notice that f(x) = f(x+1) therefor the code from above won't work correctly in this case.

I need help to find a solution for that case.

Read more »

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