How to return the correct value when Divide and Conquer Algorithm(for 1-D Closest Pairs) has done its job?

Question

I need to find the closest pair of numbers of an integer array. For example: If I have {25, 13, 59, 7, 16} numbers, my result should be |13 - 16| = 3. So I try to solve the problem using Divide and Conquer Algorithm. But when I get differences of numbers from sub-problems, I can't store and compare them. I see where my program goes wrong when I debug it but couldn't find any solution for hours.

Here is my function:

int closestPairs(int list[], int first, int last)
{
    if (last - first == 1)
        return 0;
    else if (last - first == 2)
        return abs(list[first] - list[last - 1]);

    int median = (first + last) / 2;

    int left = closestPairs(list, first, median);
    int right = closestPairs(list, median, last);

    int temp = abs(list[first] - list[last - 1]);

    if (abs(left - right) < temp)
        temp = abs(left - right);

    return temp;
}

And here is the driver function:

int main()
{
    int list[] = { 34, 23, 48 , 4, 66, 69};
    int n = sizeof(list) / sizeof(int);
    cout << closestPairs(list, 0, n) << endl;

    return 0;
}

So how can I store the value obtained from abs(left - right) and see if it's less or greater than the next value? Or am I wrong all over and doing everything wrong? Thanks in advance.

Answer 1

It seems to me that the concepts of using recursion to find the solution and storing a value for comparison to the next iteration are opposing concepts in this case. Storing a variable for comparison in a recursive function seems like it would be a bit of a mess (and require some significant restructuring of your code). The idea as I understand it of your divide and conquer algorithm is to take a big list of ints and divide it into smaller lists and allowing the best possible answer to make its way up through the chain. Here's the way I see this working based on your code (using mostly pseudo code):

int FindClosest(int list[],int first,int last)
{
     if(number of elements in list == 2)
     {
         return (int2 - int1)
     }
     if(number of elements in list == 3){
     {
         if((int3-int2)<(int2 - int2))
             return (int3-int2)
         else
             return (int2-int1)
     }
     if(number of elements in list >3)
     {
         subList1 = oneSubGroupofElements(list)
         subList2 = anotherSubGroupofelements(list)
         if(FindClosest(subList1)<FindClosest(subList2))
              return Findclosest(subList1)
         else
              return FindClosest(subList2)
     }
}

There is another issue with this method which you can see for lists with more than 2 elements, that is because your result relies on pairwise neighbours, you must consider that you can't just split the list in half. For example:

int list[] = {1,4,5,9}

would cause problems if you simply split the list into two lists of two elements as the difference between 4 and 5 would not be considered (which would be the correct answer). Your sublists would have to include the overlap so that at least one of the sublists returns 5-4 when called from FindClosest.