题目来源 : 《编程之美》 2.12 快速寻找满足条件的两个数， Page 177

【问题描述】

      快速找出一个长度为 N 的数组 A 中的两个数字，让这两个数字的和为一个给定的数字 S 。

【伪代码】

1 sort(A) // ascending order, O(N*logN) 2  3 int i = 0, j = N - 1;   4 while (i < j) { 5     if (A[i] + A[j] == S) { 6         The answer has been found !!! 7         break; 8     } else if (A[i] + A[j] < S) { 9         i++;10     } else {11         j--;12     }13 }14 15 The answer does not exsit !!!

      时间复杂度： O（N*logN） + O(N) = O(N*logN)

【形式化证明】

      循环不变式：

　　　

 

　　　　1. 在第一轮迭代之前，不变式显然成立。

　　　　2. 设前 k 轮迭代能够保持不变式成立， 则在 k+1 轮：

　　　　　　(1) 若找到答案，则结束循环；

　　　　　　(2) 否则，由于数组是有序的并且前 k 轮不变式成立，在执行 i++ （ln 9）或 j-- （ln 11）后，不变式仍成立。 

　　　　3. 循环结束后，若未找到答案，则 i = j, 由循环不变式可知不存在所要求的答案