Algoritmo O(m+n) per l'interpolazione lineare

Question

Problema

Dati dati costituiti da $n$ coordinate $\sinistra((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\destra)$ ordinati per loro $x$-valori e $m$ punti di query ordinati $(q_1, q_2, \ldots, q_m)$, trovare i valori interpolati linearmente dei punti di query in base ai dati.Assumiamo $q_i \in (\min_j x_j, \max_j x_j)$

Ho sentito dire che questo problema potrebbe essere risolto $O(m+n)$ tempo ma riesco solo a pensare a un $O(m \log n)$ algoritmo.Non riesco a trovare questo particolare problema in nessuno dei libri di testo sugli algoritmi.

Algoritmo lineare

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)

Questo ci dà un tempo di esecuzione di $O(m \log n)$, non mi è chiaro come arrivare a questo $O(m + n)$ come la ricerca di $x_i$ deve essere fatto per ogni punto di query.

Answer 1

È sufficiente eseguire la ricerca binaria per il primo elemento e quindi scorrere simultaneamente i punti dati e i punti query.

Pseudocodice

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)