user3393266 user3393266 - 11 days ago 6
C Question

Recursively splitting an array in C

I'm trying to come up with a divide-and-conquer algorithm for finding the minimum element in an array but recursive code is a bit mind bending to me.

For example, taking the following pseudo code:

procedure R_MIN (A, n)
begin
if (n = 1) then
min := A[0];
else
lmin := R_MIN (A, n/2);
rmin := R_MIN (&(A[n/2]), n - n/2);
if (lmin < rmin) then
min := lmin;
else
min := rmin;
endelse;
endelse;
return min;
end R_MIN


The way I understand it is we split the array in half, unless we have the base case. Then we figure out which half has the min and repeat the call, further splitting it (now we have 4 arrays). But where and how is the min actually found and what would this code look like in C? It seems to me this would only work when we have split into pairs.

Answer

It finds the minimum from the previous recursive calls on the left and right halves of the array. When the base case is reached and the array has length 1, then that is the minimum of that sub-array of length 1. This minimum is then taken and compared with the minimum of the other half. The lower of the two is the minimum of this sub-array. This is returned to be compared and so on...

If you translate the pseudo-code to C:

#include <stdio.h>

int rec_min(int A [],int len)
{
  int min,lmin,rmin;
  if(len==1)
    return A[0];
  else
  {
    lmin=rec_min(A,len/2);
    rmin=rec_min(A+len/2,len-len/2);
    if(lmin<rmin)
      return lmin;
    else
      return rmin;
  }
}

int main()
{        
  int test [10]={3,2,7,4,5,8,1,9,6,10};

  printf("%d\n",rec_min(test,10));

  return 0;
}