CODEWITHSUNDEEP
algorithm
Elad Weiss
Elad Weiss

Reputation: 4002

Finding a pair with a given sum in a sorted array - is there a correctness proof?

I saw the 2 pointer algorithm in dozens of posts, i.e:

l = 0;
r = n - 1;

while (l < r)
    sum = A[l] + A[r];
    if (sum == expected) return true;
    elif (sum < expected) l++;
    else r--;

I know it works. I even solved it myself in an interview. But I couldn't find anywhere a correctness proof, or even an intuitive explanation to why it works.

Can someone provide an explanation or link to one?

Thanks

Upvotes: 2

Views: 716

Answers (1)

MBo
MBo

Reputation: 80287

Imagine 2D array where B[i,j] = A[i] + A[j]. Note that all the numbers in the array are in increasing order from left to right and from top to bottom.

Set l=0, r=n-1 - this is right top corner of the whole 2D array, element B[0,n-1], and start search.

For every index pair (l, r) we can see three opportunities (I omit check for pointer intersections):

Sum to found X = B[l,r] => So we have found needed indexes. Exit.

X < B[l, r] => Due to the sorted order of column, all elements of this column are too large, so we can exclude this column, and decrement r (move left)

X > B[l, r] => Due to the sorted order of row, all elements of this row are too small, so we can exclude this row, and increment l (move down)

Note that at every step we stay in the right top corner of subarray with possible solutions, that is why two last cases work

Upvotes: 4

Related Questions