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).