Minimum of a Convex Function
Problem statement
Find the minimum value of a convex function on a finite integer domain.
For this practice interface, values[i] supplies the exact value f(i) for every integer index from 0 through values.length - 1. The differences values[i+1] - values[i] never decrease as i increases. This is what makes the samples convex on this integer domain. The minimum may occur at an endpoint or across a flat interval.
Return the minimum function value. After a linear-scan baseline, use the convex shape to narrow the candidate interval with ternary search. All function values are supplied in the array. There is no limit on how many values you may read, and you do not need to estimate values between integer indices.
Function
minimumConvexValue(values: int[]) → intExamples
Example 1
values = [9,4,1,0,1,4,9]return = 0The minimum sample is f(3) = 0.
Example 2
values = [1,4,9]return = 1The convex function is increasing on this domain, so its first value is minimal.
Example 3
values = [4,2,2,2,3]return = 2The minimum value is 2 across a flat interval; return the value rather than an index.
Constraints
1 <= values.length <= 5000.-10^9 <= values[i] <= 10^9.- For every valid
i,values[i+1] - values[i] <= values[i+2] - values[i+1].