How Divide and Conquer algorithms work with a given input?

Question

I've written a divide and conquer algorithm in java. The problem is, I've tested it an it works, except I'm not really sure why or what it does with the data. I know the it splits the array into sub parts, but apart from that i'm confused what happens what they're returning everything. For example, does the smallest base case return its number and compare that? Also what order does the recursive take place if theres more than one recursion call in a function? My code is:

public static int FindMin(int[] array, int low, int high)
{
int min = 0, min1 = 0, min2 = 0;
int mid = 0;
if (low == high)
    {
    min = array[low];
    }
else if (low == (high - 1))
    {
    if (array[low] < array[high])
        {
        min = array[low];
        }
    else if (array[low] > array[high]);
        {
        min = array[high];
        }
    }
else
    {
    mid = (low + high)/2;
    min1 = FindMin(array, low, mid);
    min2 = FindMin(array, mid+1, high);
    if (min1 < min2)
        {
        min = min1;
        }
    else
        {
        min = min2;
        }
    }
return min;
}

Basically what I want to know is: how the algorithm would work if it was given the input: 3,6,1,5,7,2,1. Like what it returns and things like that.

I'm sorry if the question is somewhat ambiguous but I know how to code it, I just cant seem to understand how it returns everything, regardless of all the google pages and pdfs i've started at.

Thanks for all the help anyway! :D

Answer 1

While a debugger is useful, sometimes the right sort of logfile output can provide more insight. I added a call to the following function at the end of your FindMin() function, just before the return min; statement:

public static void pr (int[] array, int low, int high, int min) {
    System.out.print("low = ");
    System.out.print(low);
    System.out.print(", high = ");
    System.out.print(high);
    System.out.print(", array = ");
    for (int i = low; i <= high; i++) {
        System.out.print(array[i]);
        if (i < high) {
            System.out.print(",");
        }
    }
    System.out.print(" min = ");
    System.out.print(min);
    System.out.print("\n");
}

The output I get is:

low = 0, high = 1, array = 3,6 min = 6
low = 2, high = 3, array = 1,5 min = 5
low = 0, high = 3, array = 3,6,1,5 min = 5
low = 4, high = 5, array = 7,2 min = 2
low = 6, high = 6, array = 1 min = 1
low = 4, high = 6, array = 7,2,1 min = 1
low = 0, high = 6, array = 3,6,1,5,7,2,1 min = 1

This tells me that, although FindMin() is returning the correct answer for this test case, it is doing so somewhat by accident. I'm looking now to see why ...

(EDIT)

One issue is that the code:

if (array[low] < array[high])
{
    min = array[low];
}
else if (array[low] > array[high]);  // <- stray semi-colon here
{
    min = array[high];
}

... does not consider the case where array[low] == array[high]. Either the first comparison should be <= or the second should be >=, otherwise there will be cases where the returned value of min will be its initialised value of 0 because neither of the branches of the if will apply.

(FURTHER EDIT)

You have a stray semi-colon that is causing your bug. The semi-colon after the test that I've marked above terminates the statement. That prematurely terminated else if is then followed by another statement that always sets min to equal array[high] regardless of the preceding tests.

Changing this code to:

if (array[low] < array[high])
    {
    min = array[low];
    }
else 
    {
    min = array[high];
    }

... gives the following output:

low = 0, high = 1, array = 3,6 min = 3
low = 2, high = 3, array = 1,5 min = 1
low = 0, high = 3, array = 3,6,1,5 min = 1
low = 4, high = 5, array = 7,2 min = 2
low = 6, high = 6, array = 1 min = 1
low = 4, high = 6, array = 7,2,1 min = 1
low = 0, high = 6, array = 3,6,1,5,7,2,1 min = 1

... which you can see is producing the correct result from each recursive call.

Answer 2

Okay, so now I got a grasp what it does and how it works.

It's quite simple. For a given array, you divide it into two parts further and further. Now every recursive code has to stop at some point, yours stop in two situation.

A) When the part this recursive needs to process is sized one.
B) When the part this recursive needs to process is sized two.

So when condition A is met, your function simply returns low, which is equal to high.

When condition B is met, your function compares array[low] and array[high], and returns the index of the value which is lower.

If the recursive function has to process a range of more than 2, it divides into two part, and hand those two part to two more recursive parts.

For example, for a given array like this.

array[] = {1, 2, 3, 4, 5}

You will first split it to two parts of {1, 2} [0...1] and {3, 4, 5} [2...4].

    And now since the first part is of size 2, the index 0 gets returned because 1 is smaller than 2, obviously.

    And then the other part {3, 4, 5} gets divided again, to two parts, {3} [2...2], and {4, 5} [3...4].

        The first subpart of sized one, gets returned immediately, because it's of size one, return value = 2.

        And then the second part which is sized two, get compared and returned, return value = 3.

    Now these two return values (2 and 3) gets processed, comparing array[2] and array[3], array[2] is definitely smaller, so it returns 2.

Now those two return values (0 and 2) gets processed, comparing the two, we can see the minima is at index 0, of value 1.

There's a flaw in your code, at the last part, you should compare array[min1] and array[min2] and return min1 or min2.

It's quite a mess, hope you can understand. Another things is my syntax, {data}[index range]