Piecewise Linear Interpolation with Extrapolation

Implement: linear_interpolate(n, x_knots, y_knots, x_input) -> float You are given n unordered two-dimensional knots (x_knots[i], y_knots[i]). Sort them by x-coordinate and connect adjacent points with line segments, defining a piecewise linear function LI(x). Return LI(x_input): interpolate using adjacent endpoints when x_input lies between two knots; extrapolate using the line through the leftmost two knots if it is smaller than every x-coordinate; extrapolate using the line through the rightmost two knots if it is larger than every x-coordinate; return the knot's y-coordinate when x_input equals a knot x-coordinate. Constraints: 2 <= n <= 2 * 10^5; all x-coordinates are distinct; no interpolation libraries may be used. Target complexity: O(n log n) preprocessing and O(log n) for the query. Example Input n=3, x_knots=[2, 0, 1], y_knots=[4, 0, 1], x_input=0.5 Output 0.5