I have been puzzling over an algorithm that decides whether a sorted array of numbers contains two numbers that differ by k
. I do not intuitively understand why this algorithm works, or what thought process might have led me to think of this algorithm on my own, although I believe that I can prove it's correctness.
CONTAINS_DIFFK(arr, k)
n = size(arr)
if n == 1 return false
i = 1
j = 2
while i <= n and j <= n
if i != j and arr[j] - arr[i] == k
return true
if arr[j] - arr[i] < k
j++
else
i++
return false
My questions are:
- Is the following proof sound
- Is there a more concise way to prove correctness?
- What thought process might have lead me to derive this algorithm on my own? (I had to look up the solution)
Proof by Induction
Let arr
be an arbitrary sorted array of integers of length n
. Assume for the sake of induction that CONTAINS_DIFFK
return true
if arr
contains two numbers which differ by k
and false
otherwise. Let arr'
be an arbitrary sorted array formed by adding a single arbitrary integer to the end of arr
. We prove that CONTAINS_DIFFK
return true
if arr'
contains two numbers which differ by k
and false
otherwise.
Assume that it is the case that arr
contains two elements that differ by k
. By our inductive assumption, CONTAINS_DIFFK
will return true
for arr
. Because CONTAINS_DIFFK
immediately returns after finding two elements that differ by k
without considering further elements, and the first n
elements of arr
and arr'
are identical, the n+1
'th element of arr'
will not be considered and will not affect the output of the algorithm. Thus CONTAINS_DIFFK
returns true
for input arr'
.
Therefore we need only consider the case, which is now assumed, in which arr
did not already contain two elements which differ by k
. We must consider the cases in which the n+1
'th element of arr'
does not differ from any of the first n
elements by k
and the case in which it does.
First, consider the case in which the n+1
'th element of arr'
does not differ from any of the first n
elements of arr'
. We show that the algorithm returns false
. Let i'
be the value of i
when j
is incremented to be equal to n+1
. Note that i' <= n
. Now simply note that the last element of arr'
will be compared to some subset of the elements after and including the i'
th element. Since we assumed that the last element of arr'
does not differ from any element by k
, the condition for returning true
will never be met and false
will be returned.
Finally, we consider the case in which there exists some element e
in arr
which differs by k
from the n+1
'th element of arr'
, and show that the algorithm returns true
. Again, let i'
be the value of i
when j
is incremented to n+1
while processing arr
. Now, critically, note that j
was incremented to n+1
because arr[n] - arr[i'] < k
. If we note also that arr'[n+1] >= arr'[n]
(because it is sorted) and arr'[n+1] - e = k
, then we may derive e > arr[i']
. Thus, we note that i
will be increased from i'
up to the index of e
at which point CONTAINS_DIFFK
will return true
as desired.
Base case
Let arr
be an arbitrary sorted array of two integers. We may trace through the execution of this algorithm and note that if arr[2] - arr[1]
then it will return true
and it will return false
otherwise. Thus, the induction is complete.