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