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

• Are query points sorted? – Vladislav Bezhentsev May 31 '20 at 14:01
• 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? – James Cagalawan May 31 '20 at 14:14
• 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. – Vladislav Bezhentsev May 31 '20 at 14:31
• Yeah, that's what I meant. – James Cagalawan May 31 '20 at 14:38
• I've edited the question to add the sorted assumption on the query points, thanks Vladislav. – James Cagalawan May 31 '20 at 15:18

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)