How to find the difference of two numbers in an array recursively?

Question

Java

Friends, I solved recursion problems on the Internet, I came across two that the brain can’t handle in any way: 1) find two elements in an ordered array with a difference of 10, using recursion and O (n) time. 2) Find the same two elements recursively, but the array is not ordered. Any ideas? In what direction to move?

Answer 1

It could have been something like this:

static int pres,qres;
static int[] A;
static int M=10;

bool Find1(int p,int q){
  if(A[q]-A[p]==M){ 
    pres=p; qres=q;
    return true;
  }
  if(A[q]-A[p]<M || q-p<2) return false;  
  int k=p+(q-p)/2;
  if(Find1(p,k) || Find1(k,q)) return true;
  return Find2(p,k,k+1,q);
}

bool Find2(int p1,int q1,int p2,int q2){  // p1<=q1<p2<=q2
  if(A[p2]-A[q1]>M || A[q2]-A[p1]<M) return false;
  if(A[p2]-A[p1]==M){
    pres=p1; qres=p2; return true;
  }
  if(A[p1]==A[q1] && A[p2]==A[q2]) return false;
  if(A[q1]-A[p1]>A[q2]-A[p2]){
    int k=p1+(q1-p1)/2;
    return Find2(p1,k,p2,q2) || Find2(k+1,q1,p2,q2);
  }else{
    int k=p2+(q2-p2)/2;
    return Find2(p1,q1,p2,k) || Find2(p1,q1,k+1,q2);
  }
}

(function Find1 looks for a pair in one fragment, Find2 - in two disjoint fragments). But I have absolutely no idea how difficult it will be. It is possible that O(n*log(n)). But the recursion is used for its intended purpose :)
UPD. Slightly corrected the conditions - here it is often better to compare not the indices, but the elements themselves.

Answer 2

Offhand:

const D = 10
int N = ...
int a[N] = ...

find(i, j, N):
  d := a[j] - a[i]
  if d = D then
    return (i, j)
  else if d < D then
    if j + 1 == N then
      return nil
    else
      return find(i, j + 1, N)
    end
  else if d > D then
    if i + 1 == N - 1 then
      return nil
    else
      return find(i + 1, j, N)
    end
  end

find(0, 1, N);

Complexity in theory O(2n). In general, it’s not very beautiful for a recursive implementation, but it seems to be a working option.
The second task is yourself.

Answer 3

Freelance