Обобщение простого алгоритма линейного времени

Question

Я пытаюсь написать линейный алгоритм времени O (n), который дал таблицу A [0..n-1] (заполненную восходящими натуральными значениями) проверяет, есть ли пара A [i], A [j], который удовлетворяет f (A [i], A [j]) = C (C является предварительно определенной константой) .

Предположим, что f (a, b) = a + b, алгоритм будет иметь вид:

Algo Paires(A[0..N-1], C)
in: Tab A[0..n-1] and C a constant
out : Boolean
Init indice ← 0
For i ← 0..n-1 do 
    if indice ≠ i & A[indice] + A[i] = C 
      return true
    else if i = n-1 & indice ≤ n-2 
      indice++; i ← 0;
End for
return False

Но если:

Каким будет алгоритм тогда? какие-либо предложения?

Answer 1

Подсказка: предположим, что существует двумерная матрица, строки и столбцы которой отсортированы, и вам дано число x, которое вам нужно найти ...