Stephen Docy made a great job tracing the program's execution and explaining the rationale behind its decisions. Maybe making the answer closer to a mathematical proof of the algorithm's correctness could make it easier to generalize to problems like the one mentioned by zzzzzzz in the comments.
We are given a sorted array A
of length n
and an integer sum
. We need to find if there are any two indices i
and j
such that i != j
and A[i] + A[j] == sum
.
The solutions (i, j)
and (j, i)
are equivalent, so we can assume that i < j
without loss of generality. In the program, the current guess at i
is called l
and the current guess at j
is called r
.
We iteratively slice the array till we find a slice that has the two summands that sum to sum
at its boundary, or we find there is no such slice. The slice starts at index l
and ends at index r
and I will write it as (l, r)
.
Initially, the slice is the whole array. In each iteration, the length of the slice is decreased by 1: either the left boundary index l
increases or the right boundary index r
decreases. When the slice length decreases to 1 (l == r
), there are no pairs of different indexes inside the slice, so false is returned. This means that the algorithm halts for any input. The O(n) complexity is also immediately clear. The correctness remains to be proven.
We can assume there is a solution; if there is none, the analysis in the above paragraph applies and the branch returning true can never be executed.
The loop has an invariant (statement that holds true regardless of how many iterations have been done yet): When a solution exists, it is either (l, r)
itself or its sub-slice. Mathematically, such an invariant is a lemma -- something that is not very useful by itself but makes a stepping stone in the overall proof. We get the overall correctness by initially making (l, r)
the whole array and observing that as each iteration makes the slice shorter, the invariant ensures that we will eventually find the solution. Now, we just need to prove the invariant.
We will prove the invariant by induction. The induction base is trivial -- the initial slice (l, r)
either is the solution, or contains it as a sub-slice. The hard part is the induction step, i.e. proving that when (l, r)
contains the solution, either it is the solution itself or the slice for the next iteration contains the solution as a sub-slice.
When A[l] + A[r] == sum
, (l, r)
is the solution itself; the first condition in the loop is triggered, true is returned, and everyone is happy.
When A[l] + A[r] > sum
, the slice for the next iteration is (l, r - 1)
, which still contains the solution. Let's prove that by contradiction, assuming (l, r - 1)
does not contain the solution. How could that happen, when (l, r)
contained the solution (by induction hypothesis)? The only way would be that the solution (i, j)
has j == r
(r
is the only index we removed from the slice). Because by definition A[i] + A[j] == sum
, we get A[i] + A[r] == sum < A[l] + A[r]
in this branch. When we subtract A[r]
from both sides of the inequality, we get A[i] < A[l]
. But A[l]
is the smallest value in the (l, r)
slice (the array is sorted), so this is a contradiction.
When A[l] + A[r] < sum
, the slice for the next iteration is (l + 1, r)
. The argument is symmetric to the previous case.
∎
The algorithm may be easily rewritten as recursive, which simplifies the analysis at the expense of actual performance. This is the functional programming approach.
#define lli long long
//n is size of array
bool f(lli sum) {
return g(sum, 0, n - 1);
}
bool g(lli sum, int l, int r) {
if ( l >= r ) return 0;
else if ( A[l] + A[r] == sum ) return 1;
else if ( A[l] + A[r] > sum ) return g(sum, l, r - 1);
else return g(sum, l + 1, r);
}
The f
function still contains the initialization, but it calls the new g
function, which implements the original loop. Instead of keeping the state in local variables, it uses its parameters. Each call of the g
function corresponds to a single iteration of the original loop.
The g
function is a solution to a more general problem than the original one: Given a sorted array A, are there any two indices i
and j
such that i != j
and A[i] + A[j] == sum
and both i
and j
are between l
and r
(inclusive)?
This makes reading the analysis even simpler. The loop invariant is actually the proof of correctness of g
and the structure of g
guides the proof.
start
andend
pointers.C
orC++
?