O(nlogn) 算法来搜索两个数组中两个元素的总和

Question

给定两个排序的整数数组 A1、A2，具有相同的长度n和一个整数x，我需要编写一个以 O(nlog(n)) 运行的算法，该算法确定是否存在两个元素a1, a2（每个数组中的一个元素）使a1+a2=x.

起初我想有两个索引迭代器i1=0, i2=0（每个数组一个）从 0 开始，一次增加一个，这取决于 A1 的下一个元素比 A2 的下一个元素大/小。但是在两个阵列上对其进行测试后，我发现它可能会遗漏一些可能的解决方案......

Answer 1

好吧，因为它们都已经排序了，所以算法应该是 O(n)（排序是 O(n * log(n))）：

i1 = 0
i2 = A2.size - 1
while i1 < A1.size and i2 >= 0
    if A1[i1] + A2[i2] < x
        ++i1
    else if A1[i1] + A2[i2] > x
        --i2
    else
        success!!!!