Implement monotonic-array linear interpolation

Implement a function to **interpolate** a y-value for a query x-value given paired data points. You are given: - `array_x`: a **strictly increasing** list of x-values (monotonic), length `n >= 2` - `array_y`: list of y-values of the **same length** - `x`: a query number that may be **inside or outside** the range of `array_x` ### Tasks 1. Write `interpolate(array_x, array_y, x)` that returns the **linearly interpolated** y-value when `x` is within the domain. - If `x == array_x[i]`, return `array_y[i]` exactly. - Otherwise, find the two surrounding points `(x0,y0)` and `(x1,y1)` such that `x0 < x < x1` and return linear interpolation. 2. Discuss and/or implement behavior when `x` is **outside** `[array_x[0], array_x[-1]]`: - Option A: raise an error (no extrapolation) - Option B: clamp to the nearest boundary y-value - Option C: extrapolate (e.g., extend the nearest segment linearly) 3. Follow-ups - Instead of raising an error, what other values could be returned (e.g., `None`, `NaN`), and when is that appropriate? - In which real-world cases does each out-of-range behavior make sense (pros/cons)? - For `x = 100` and `array_x = [2,4,6,8,11]`, what is the safest behavior and why? - Name an alternative implementation strategy besides using binary search (`bisect`). ### Constraints - Target time complexity: **O(log n)** for in-range queries (preferred). - Handle edge cases (very small arrays, exact matches, float precision).