Implement monotonic x-y linear interpolation

Implement a function `interpolate(array_x, array_y, x)` that returns the interpolated y-value at query point `x`. You are given: - `array_x`: a strictly increasing (monotonic) list/array of floats (length n ≥ 2) - `array_y`: a list/array of floats of the same length as `array_x` - `x`: a float query that may be inside or outside the range `[array_x[0], array_x[n-1]]` Requirements: 1) If `x` is within the domain, return the **piecewise-linear interpolation** between the two neighboring points. 2) Discuss and optionally support behaviors when `x` is out of range: - Raise an error (no extrapolation) - Clamp to the nearest endpoint - Extrapolate linearly (e.g., extend the last segment) 3) Analyze time complexity and give at least one alternative to a binary-search (bisect) approach. Assume `array_x` has no duplicates and both arrays fit in memory.