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 : ↵
↵
![ ](/predownloaded/ce/ee/ceee97367c07bea39ace6a69d8e9154e866532b7.png)↵
↵
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.↵
↵
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;↵
↵
}↵
↵
↵
![ ](/predownloaded/ce/ee/ceee97367c07bea39ace6a69d8e9154e866532b7.png)↵
↵
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.↵