O (m + n) algoritmo para interpolación lineal

Question

Problema

Dados los datos que consisten en $ n $ coordenadas $ \ izquierda ((x_1, y_1), (x_2, y_2) , \ ldots, (x_n, y_n) \ derecha) $ ordenados por su $ x $ -values, y $ m $ Puntos de consulta ordenados $ (q_1, q_2, \ ldots, q_m) $ , encuentre los valores linealmente interpolados de los puntos de consulta de acuerdo con el datos. Asumimos $ q_i \ in (\ min_j x_j, \ max_j x_j) $

Escuché que este problema podría resolverse en $ o (m + n) $ tiempo, pero solo puedo pensar en un $ O (m \ log n) $ algoritmo. Parece que no puedo encontrar este problema en particular en ninguno de los libros de texto del algoritmo.

Algoritmo linealitmico

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)

Esto nos da un tiempo de ejecución de $ o (m \ log n) $ , no me está claro cómo obtener esto a $ o (m + n) $ Como búsqueda de $ x_i $ debe hacerse para cada punto de consulta.

Answer 1

Solo necesita realizar una búsqueda binaria del primer elemento y luego iterira simultáneamente a través de los puntos de datos y puntos de consulta.

Pseudocódigo

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)