Problem Description

Implement a function interpolate(array_x, array_y, x) that calculates and returns the interpolated y-value for a given query point x.

Inputs

• array_x: A strictly increasing (monotonic) list or array of floats, with a length n where n >= 2.
• array_y: A list or array of floats of the same length as array_x.
• x: A float representing the query point. This point may be within or outside the domain defined by [array_x[0], array_x[n-1]].

Requirements

1. In-Domain Interpolation: If x falls within the domain [array_x[0], array_x[n-1]], the function must return the piecewise-linear interpolation between the two neighboring data points.
2. Out-of-Domain Behavior: Discuss and optionally implement support for the following behaviors when x is outside the domain:
   • Raise an error (i.e., no extrapolation).
   • Clamp the result to the nearest endpoint's y-value.
   • Extrapolate linearly, extending the trend of the nearest segment.
3. Performance Analysis: Analyze the time complexity of your solution. Additionally, propose at least one alternative approach to using binary search (e.g., bisect in Python) for finding the relevant interval.

Assumptions

• array_x contains no duplicate values.
• Both array_x and array_y are small enough to fit entirely within memory.