Algoritmo O(m+n) para Interpolação Linear

Question

Problema

Dados dados que consistem em $n$ coordenadas $\esquerda((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\direita)$ classificados por seus $x$-valores e $m$ pontos de consulta classificados $(q_1, q_2, \ldots, q_m)$, encontre os valores interpolados linearmente dos pontos de consulta de acordo com os dados.Nós presumimos $q_i \in (\min_j x_j, \max_j x_j)$

Ouvi de imediato que este problema poderia ser resolvido em $O(m+n)$ tempo, mas só consigo pensar em um $O(m\logn)$ algoritmo.Não consigo encontrar esse problema específico em nenhum dos livros de algoritmo.

Algoritmo Linearítmico

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)

Isso nos dá um tempo de execução de $O(m\logn)$, não está claro para mim como fazer isso $O(m + n)$ como a busca por $x_i$ deve ser feito para cada ponto de consulta.

Answer 1

Você só precisa realizar a pesquisa binária para o primeiro elemento e, em seguida, iterar simultaneamente pelos pontos de dados e pontos de consulta.

Pseudo-có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)