O (m+ n) Алгоритм линейной интерполяции

Question

Проблема

Приведенные данные, состоящие из $n$ координаты $\слева((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\справа)$ отсортированы по их $x$-ценности, и $м$ отсортированные точки запроса $(q_1, q_2, \ldots, q_m)$, найдите линейно интерполированные значения точек запроса в соответствии с данными.Мы предполагаем, что $q_i \in (\min_j x_j, \max_j x_j)$

Я слышал из первых уст, что эта проблема может быть решена в $O(m+n)$ времени, но могу думать только о $O(m \log n)$ алгоритм.Кажется, я не могу найти эту конкретную проблему ни в одном из учебников по алгоритмам.

Линеарифмический Алгоритм

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)

Это дает нам время выполнения $O(m \log n)$, мне непонятно, как свести это к $O(m + n)$ по мере поиска $x_i$ должно быть выполнено для каждой точки запроса.

Answer 1

Вам нужно только выполнить двоичный поиск для первого элемента, а затем выполнить итерацию одновременно по точкам данных и точкам запроса.

Псевдокод

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)