Searching for the minima or maxima in an array if it is not strictly convex or concave.

I know we can use binary search (or ternary search) to find the answer if the function is strictly convex or concave. But what if the function is not following that monotonicity? Can someone please tell we how to find the solution as fast as the previous case? this problem uses that.

Mostly we cant!!there’s a technique called hill climbing which can be uswd for such cases,but it doesnt guarantee optimality…

Here maybe we can use priority que,like check for each point on x axis in increasing order(only those x such that there is atleast 1 point with that x),then as we move toward right,we can remove some elements and add new elements…

1 Like

@vivek_1998299 what is the advantage of using priority queue? And how to add and remove the points from that? If possible please elaborate a little.