O(m+n) Algorithm for Linear Interpolation
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] &lt;= q[0] &lt;= x[i+1] with binary search

for q in qs:
    while not x[i] &lt;= q &lt;= x[i+1]:
        i++
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)