Divide-and-conquer approach for simple array algorithm

Question

I'm trying to make a divide-and-conquer approach that points out the first number in a list that does not follow a n+1 sequence. And if all of them do follow the sequence, return -1.

So for example, if I have an array of numbers of size 8:

int size = 9;
int listofNumbers[9] = { 4, 5, 6, 7, 8, 9, 3, 6, 7 };

I would need a function that scans the array and returns 3, since it's the first one that fails to meet the n+1 sequence.

I made an approach using iteration, and it works:

int findFirst_iterative(int list[], int listSize)
{
    if (listSize < 1)
    {
        return -1; // empty list.
    }

    int nextNumber = list[0]; // we start with the first number in the list.

    for (int i = 1; i < listSize; i++)
    {
        if (list[i] != (nextNumber + 1))
        {
            return list[i];
        }

        nextNumber = list[i];
    }

    return -1;
}

I am now trying to do the same but using a divide-and-conquer approach.

int findFirst_divideandconquer(int list[], int listSize)
{
    if (listSize < 1)
    {
        return -1; // the list is empty.
    }
    else if (listSize == 2)
    {
        if (list[1] != list[0] + 1)
        {
            return list[1];
        }
        else
        {
            return -1;
        }
    }

    int mid = listSize / 2;
    int listhalfA[mid];
    int listhalfB[mid];

    int overallindex = 0;
    for (int i = 0; i < mid; i++)
    {
        listhalfA[i] = list[overallindex];
        overallindex = overallindex + 1;
    }

    for (int i = 0; i < mid; i++)
    {
        listhalfB[i] = list[overallindex];
        overallindex = overallindex + 1;
    }

    int resultA = findFirst_divideandconquer(listhalfA, mid);
    if (resultA == -1)
    {
        int resultB = findFirst_divideandconquer(listhalfB, mid);
        if (resultB == -1)
        {
            return -1;
        }
        return resultB;
    }
    return resultA;
}

I've hit a roadblock, while I succeeded in dividing the list in halves, it will return the second number that fails to meet the sequence, instead of the first one. So the code above returns 6 instead of 3, which is what I need. How could I fix this?

If you want to do this for learning then do your thing. Otherwise, stick to the iteration solution as it already is the most efficient solution for this task. — Socowi
– Socowi, Commented Aug 19, 2021 at 23:57
Before being able to fix the issue you need to find the root cause. What debugging did you do? Did you run your code in a debugger and step thru it (or even just added more debug prints) to find where it first starts to fail? How to debug small programs. — kaylum
– kaylum, Commented Aug 19, 2021 at 23:57
int mid = listSize / 2; int listhalfA[mid]; int listhalfB[mid]; This won't work for odd sized arrays as it will miss one element - which is the case in the code shown. For odd sized arrays one half will have one more element than the other half. — kaylum
– kaylum, Commented Aug 20, 2021 at 0:57
Instead of int listhalfB[mid];, use int listhalfB[listSize - mid];. — chux
– chux, Commented Aug 20, 2021 at 2:02

Socowi · Accepted Answer · 2021-08-20 11:31:40Z

First of all, for this task there is no point in using divide and conquer other than learning. Your iterative solution is the fastest approach. Only if you wanted any non-consecutive number instead of the first one, divide and conquer could be faster.

Your divide and conquer approach has three problems. Two small bugs and a theoretical flaw:

As kaylum pointed out, int mid = listSize / 2; int listhalfA[mid]; int listhalfB[mid]; might skip an element. If listSize is odd then mid+mid < listSize because of integer division. To fix this, use int listhalfB[mid]; int listhalfB[listSize-mid];.
Your trivial case listSize < 1 should be listSize < 2. Because of the bug above this wasn't a problem so far.
Divide and conquer requires to combine the solutions of the partial problems. In your combination step, you just picked the first solution that isn't -1. But this is not sufficient. If you split the array 1, 2, 3, 11, 12, 13 into 1, 2, 3 and 11, 12, 13 you'd get the solutions -1 and -1 and therefore would return -1 even though the correct solution would be 11. The combination step needs to consider the numbers at the boundary too. An elegant way to do this is by breaking the array into two overlapping pieces 0 <= A <= mid and mid <= B <= listSize-1.

By the way: You waste a lot of code lines and execution time for copying the array. It would be easier and faster to specify start and end indices of the existing array instead:

#include <stdio.h>

int findFirstIntern(int list[], int start, int endExclusive) {
    int listSize = endExclusive - start;
    if (listSize < 2) {
        return -1;
    } else if (listSize == 2) {
        if (list[start+1] != list[start]+1) {
            return list[start+1];
        }
        return -1;
    }
    int mid = start + listSize/2;
    int result = findFirstIntern(list, start, mid+1);
    if (result != -1) {
        return result;
    }
    return findFirstIntern(list, mid, endExclusive);
}

int findFirst(int list[], int listSize) {
    return findFirstIntern(list, 0, listSize);
}

int main() {
    int list[] = {4, 5, 6, 7, 8, 9, 3, 6, 7};
    int first = findFirst(list, sizeof(list)/sizeof(int));
    printf("First non-consecutive number is %d\n", first);
    return 0;
}

If you return the index of the non-consecutive number instead of the number itself, this solution would also work with negative numbers.

Collectives™ on Stack Overflow

Divide-and-conquer approach for simple array algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related