O(m+n) Algorithm for Linear Interpolation

Question

Problem

Given data consisting of $n$ coordinates $\left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\right)$ sorted by their $x$-values, and $m$ sorted query points $(q_1, q_2, \ldots, q_m)$, find the linearly interpolated values of the query points according to the data. We assume $q_i \in (\min_j x_j, \max_j x_j)$

I heard off-hand that this problem could be solved in $O(m+n)$ time but can only think of an $O(m \log n)$ algorithm. I can't seem to find this particular problem in any of the algorithm textbooks.

Linearithmic Algorithm

interpolated = []
for q in qs:
 find x[i] such that x[i] <= q <= x[i+1] with binary search
 t = (q - x[i]) / (x[i+1] - x[i])
 interpolated.append(y[i] * (1-t) + y[i+1] * t)

This gives us a runtime of $O(m \log n)$, it's unclear to me how to get this down to $O(m + n)$ as the search for $x_i$ must be done for every query point.

• Vladislav Bezhentsev: Are query points sorted?
• James Cagalawan: Let's assume yes. I see where you're going now, you go through the sorted data points and the query points at the same time meaning you only have to do a full search once. The rest of the query points are handled by traversal. Is that right?
• Vladislav Bezhentsev: I'm not sure, what do you mean by " The rest of the query points are handled by traversal." But yes, the idea is to iterate through data and query points simultaneously using two pointers. This is the same idea which is used in the merge step of merge sort algorithm.
• James Cagalawan: Yeah, that's what I meant.
• James Cagalawan: I've edited the question to add the sorted assumption on the query points, thanks Vladislav.

Answer 1

You only need to perform binary search for the first element and then iterate simultaneously through the data points and query points.

Pseudocode

interpolated = []
find x[i] such that x[i] <= q[0] <= x[i+1] with binary search
for q in qs:
 while not x[i] <= q <= x[i+1]:
 i++
 t = (q - x[i]) / (x[i+1] - x[i])
 interpolated.append(y[i] * (1-t) + y[i+1] * t)