How could we prove the correctness of the algorithm?

Question

Consider two sets $D=\{ d_1, d_2, \dots, d_n\}$ and $E=\{ e_1, e_2, \dots, e_m \}$ and consider an other variable $K \geq 0$. Show that we can answer in time $O((n+m) \lg (n+m))$ the following question: Is there is a pair of numbers $a,b$ where $a \in D, b \in E$ such that $|a-b| \leq K$?

The algorithm should answer the above question with YES or NO. Describe the algorithm, show its correctness and show that its time complexity is $O((n+m) \lg (n+m))$.

I wrote the following algorithm:

int binary_search(int A[], int key, int low, int high, int K) 
{ 
   if (high < low) return 0; 
   else{ 
       int mid=low+floor((high-low)/2); 
       if (A[mid]<key-K) return binary_search(A, key, mid+1, high); 
       else if (A[mid]>k+key) return binary_search(A, key, low, mid-1 ); 
       else return mid; 
   } 
} 



Algorithm(D,E,K) {
  HeapSort(E); 
  low=1; 
  high=m; 
  i=1; 
  p=0 
  while (i<=n and p==0){ 
         p=binary_search(E, D[i], low, high, K ); 
         i++; 
  } 
  if (p==0) printf("NO \n"); 
  else printf("YES \n"); 
} 

We can prove the correctness of binary_search as follows, right?

Base case:

We suppose that we have an array of size 1.

Then it holds $low=high=mid$.

If the if-statement holds then we call the function binary_search(A, key, low+1, low) and since $high<low$, the function will return $0$. The result is right, because we have only one element that does not satisfy the desired property , we are looking further for an other elemenent,but since there is no other one, it means that the desired element doesn't exist.

Similarly for the case when the else-if-statament holds.

Furthermore, no matter which sie the array has, if the element we are looking at has the desired property, then the else-statement holds,so the algorithm returns the right position.

Induction hypothesis:

We suppose that binary_search gives the right result for arrays with size $<n$.

Induction step:

Now we consider an array of size $n$. If the if- or else-if statement holds, we call the binary_search for an array of size $<n$, so from the induction hypothesis we know that we will have the right result.

Otherwise, we will have the right result, from the base-case.

But how can we prove the correctness of the algorithm Algorithm?

EDIT: That's what I thought when I wrote the algorithm:

We sort the array E in order to call the binary_search that will return $0$ if there are no two elements $a,b$ of $D,E$ such that $|a-b| \leq K$ or the position at which the element of $E$ is, which we subtract with an element of D and become a difference by absolute value that is less or equal to $K$. So if the binary_search returns 0, the algorithm will return N0, otherwise it will return YES.

Answer 1

You seem to be basically on the right track already.

To prove correctness, a good first step is to prove that the algorithm will always terminate. From the behavior of i and the condition of the while loop you can deduce that the while loop can only execute a finite number of times. So as long as the binary search always terminates in finitely many steps, the algorithm terminates.

Now show that if there are elements $a \in D$ and $b \in E$ such that $|a - b|< K$, then sometime during the loop it will happen that D[i] is equal to $a$, and when that happens your binary search will return non-zero. (You don't have to show that the binary search will actually "find" that particular value of $b$ in $E$, just that it can't return zero when $E$ contains such an element.)

On the other hand you also have to show that if your algorithm returns YES then there were in fact $a \in D$ and $b \in E$ such that $|a - b|< K$. You can do this by working backward: if it returned YES then p must have been non-zero at some point in time, which means the binary search returned something that wasn't zero, which means ... .

Whether you have to prove each of these things inductively depends on the prescribed style of proof. In fact, exactly how you write the proof depends a lot on the specific proof style that you're supposed to use. In some styles the proof consists almost entirely of mathematical formulas, in others it consists mostly of text. (It looks like you're allowed to use mostly text.)

You probably want to work out the details more carefully than the above description, which is really just a general roadmap intended to give you confidence to proceed.