Proof of correctness of this algorithm

Question

Assume $A$ is an array that contains sorted integers , ie $\forall\ i,j$ where 1ドル \le i \le j \le |A|,ドル $A_i \le A_j$. The numbers do not have to be unique, and the task is to check if there is at least one pair of indices $i$ and $j$ where $A_i + A_j = n$. Simple enough, here's an algorithm that does it:

CheckForPair(A, n, i, j):
 if i >= j or outOfBound:
 return false
 v := A[i] + A[j]
 if v = n:
 return true
 if v < n:
 return CheckForPair(A, n, i + 1, j)
 if v > n:
 return CheckForPair(A, n, i, j - 1)
CheckForPair(A, n):
 return ChcekForPair(A, n, 1, |A|)

Mathematically,

$$ \begin{align} CheckForPair(A, n, i, j) &= \begin{cases} false & \text{if $i \ge j$ or $i < 1$ or $j > |A|,ドル} \\ true & \text{if $A_i + A_j = n,ドル} \\ CheckForPair(A, n, i + 1, j) & \text{if $A_i + A_j < n,ドル} \\ CheckForPair(A, n, i, j - 1) & \text{if $A_i + A_j > n$} \\ \end{cases} \\ \\ CheckForPair(A, n) &= CheckForPair(A, n, 1, |A|) \end{align} $$

This is an algorithm I have seen somewhere else and I am trying to prove its correctness. For $i$ and $j$ that are on the very ends on the array (ie $i = 1$ and $j = |A|$), it's easy to see why it is correct since:

• if $A_i$ + $A_j < n,ドル then $i$ must increase because $j$ cannot increase.
• if $A_i$ + $A_j > n,ドル then $j$ must decrease because $i$ cannot decrease.

However, for $i$ and $j$ that are in between, I fail to see why the above still holds.

Answer 1

It is a recursive definition, thus we can use induction. Let me first rephrase the algorithm a bit:

$$ CFP(n,A) = \begin{cases} False& \text{if }A=[\;]\\ True& \text{if } first(A) + last(A) = n\\ CFP(n,tail(A))&\text{if }first(A)+last(A)<n \\ CFP(n,init(A))&\text{otherwise} \end{cases} $$ where $tail(A)$ means all of $A$ but the first entry, $init(A)$ means all of $A$ but the last entry and $first(A)$ and $last(A)$ mean the first and last elements of $A$ respectively.

We now prove the statement by induction on the length of the array:

1. |A| = 0: $CFP (n,A)=False$ in accordance with the fact that there is no indices $i,j$ with $A_i+A_j=n$.
2. We assume the algorithm is correct for arrays of length $n$: Let $A$ be an array with $|A|=n+1$. If no pair of indices $i\leq j$ with $A_i+A_j=n$ exists, then either $CFP(n,A) = CFP(n,tail(A))$ or $CFP(n,A)=CFP(n,init(A)$. By induction hypothesis, the algorithm returns the correct result in both cases. On the other hand, if a pair $i\leq j$ of indices with the desired property exists, we distinguish the following cases:
   • $A_i=first(A)$: In this case, $first(A)+last(A)\geq n$ (because of how $A$ is ordered). Thus the algorithm either returns $True$ or $CFP(n,init(A))$. In the latter case $j$ is not the last index of $A,ドル thus the correctness of the result follows from the induction hypothesis.
   • $A_j = last(A)$: Analog to the previous case.
   • $first(A)<A_i\leq A_j<last(A)$: either $CFP(n,tail(A))$ or $CFP(n,init(A)$ is called. Since the a the statement is true for both $init(A)$ and $tail(A),ドル the algorithm will correctly return $True$ by induction hypothesis.

• Derek 朕會功夫: Fantastic proof!