推广一个简单的线性时间算法

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

提示:假设有一个2D矩阵,其行和列已排序,您将获得一个数字x,您需要找到它...