algorithm - 在排序数组中查找具有给定总和的一对 - 是否有正确性证明？

Question

我在很多帖子中看到了 2 指针算法，即:

l = 0;
r = n - 1;

while (l < r)
    sum = A[l] + A[r];
    if (sum == expected) return true;
    elif (sum < expected) l++;
    else r--;

我知道它有效。我什至在采访中自己解决了这个问题。但我在任何地方都找不到正确性证明，甚至找不到对其工作原理的直观解释。

有人可以提供解释或链接吗？

谢谢

Answer 1

想象一下二维数组，其中 B[i,j] = A[i] + A[j] .请注意，数组中的所有数字都是从左到右、从上到下递增的顺序。

设置l=0, r=n-1 - 这是整个二维数组元素 B[0,n-1] 的右上角，然后开始搜索。

对于每个索引对 (l, r)，我们可以看到三个机会(我省略了对指针交叉点的检查):

找到的总和 X = B[l,r] => 所以我们找到了需要的索引。退出。

X < B[l, r] => 由于列的排序顺序，该列的所有元素都太大了，所以我们可以排除该列，并递减r(左移)

X > B[l, r] => 由于行的排序顺序，这一行的所有元素都太小，所以我们可以排除这一行，并增加l(下移)

请注意，在每一步中，我们都停留在具有可能解决方案的子数组的右上角，这就是最后两种情况有效的原因