Linear Interpolation Function

Implement a function to perform linear interpolation, calculating a y-value for a given query x-value based on a set of paired data points.

Input Parameters

You will be provided with:

• array_x: A list of x-values, guaranteed to be strictly increasing (monotonic), with a length n >= 2.
• array_y: A list of corresponding y-values, of the same length as array_x.
• x: A single query number, which may fall either within or outside the range defined by array_x.

Core Tasks

1. Implement interpolate(array_x, array_y, x): This function should return the linearly interpolated y-value when x is within the domain [array_x[0], array_x[-1]].

   • If x exactly matches any array_x[i], return the corresponding array_y[i].
   • Otherwise, identify the two surrounding data points (x0, y0) and (x1, y1) such that x0 < x < x1, and perform linear interpolation between them.

2. Discuss and/or Implement Out-of-Range Behavior: Address how your function should behave when the query x falls outside the range [array_x[0], array_x[-1]]. Consider and be prepared to implement one or more of the following options:

   • Option A: Error Handling: Raise an appropriate error (e.g., ValueError) to indicate that extrapolation is not supported.
   • Option B: Clamping: Return the y-value corresponding to the nearest boundary x-value (i.e., array_y[0] if x < array_x[0], or array_y[-1] if x > array_x[-1]).
   • Option C: Extrapolation: Extend the nearest segment linearly to calculate the y-value for x.

Follow-up Discussion Points

• Beyond raising an error, what other values (e.g., None, NaN) could be returned for out-of-range queries, and under what circumstances would each be appropriate?
• Describe real-world scenarios where each of the out-of-range behaviors (Error, Clamping, Extrapolation) would be the most suitable choice, discussing their respective advantages and disadvantages.
• Given x = 100 and array_x = [2, 4, 6, 8, 11], which out-of-range behavior would be considered the safest, and why?
• Name an alternative implementation strategy for efficiently finding the surrounding points besides using binary search (e.g., bisect in Python).

Constraints

• Time Complexity: The target time complexity for in-range queries is O(log n).
• Edge Cases: The implementation must correctly handle edge cases such as very small input arrays (e.g., n=2), exact matches for x, and considerations for floating-point precision.