Array contains elements that differ by K correctness proof 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 &lt;= n and j &lt;= n
        if i != j and arr[j] - arr[i] == k
            return true
        if arr[j] - arr[i] &lt; 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' &lt;= 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'] &lt; k. If we note also that arr'[n+1] &gt;= arr'[n] (because it is sorted) and arr'[n+1] - e = k, then we  may derive e &gt; 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.
My line of thought for deriving this algo:


there is well-known Merge algo (part of Merge Sort) combining two sorted arrays
we can modify it to output only equal elements of arrays (i.e. producing intersection instead of union)
we can further modify it to return true on the first match, and false at the end
and finally, we can modify it to compare elements with given offset k


I suggest you to practice developing algos at leetcode or similar site, it will allow you to come up with similar solutions in a few minutes.