Thread: Divide & conquer find min and max by recurse

In this code nothing modify except function minMaxSearchRecursive

Code:

int min(int a, int b) {   
 if (a < b) {
        return a;
    } else {
        return b;
    }
}


int max(int a, int b) {
    if (a < b) {
        return b;
    } else {
        return a;
    }
}


typedef struct tuple {
    int min;
    int max;
} Tuple;


/**
 * Create duo value min and max, auxiliary function is already implemented for you
 */
Tuple createTuple(int min, int max);


/**
 * Function search values min and max in array 'array' help by
  * divide and conquer algorythm.
 * In array is searching in range from index 'left' to index 'right'
 */
Tuple minMaxSearchRecursive(int *array, int left, int right) {
    int halfString = 0, tmpMax = 0, tmpMin = 0;
    if(left == right){
        return createTuple(array[left], array[right]);
    }else if(right == (left + 1)){
        if(array[left] > array[right]){
            return createTuple(array[right], array[left]);
        }else
            return createTuple(array[left], array[right]);
    }/*here*/else{
        halfString = (left + right) / 2;
        minMaxSearchRecursive(array, left, halfString);
        minMaxSearchRecursive(array, halfString + 1, right);


      //  return createTuple(array[tmpMax], array[tmpMin]);
    }
}
/*Olny in this function help. For 1 or 2 value in array work correctly. But the last  *here*ELSE incorrectly. 
I don't know why using Tuple function and not int function. And how return minimum and maximum.*/

// test function, what is writed in printf is not important

void testMinMaxSearchRecursive() {
    printf("\nTest 16. rekurzivni vyhledavani minima a maxima v poli [1]: ");
    int array1[1] = {1};
    Tuple ret = minMaxSearchRecursive(array1, 0, 0);
    if (ret.min == 1 && ret.max == 1) {
        printf("OK\n");
    } else {
        printf("NOK, v poli [1] je min 1 a max 1,");
        printf(" vracite (%d, %d) != (1, 1)\n", ret.min, ret.max);
    }


    printf("Test 17. rekurzivni vyhledavani minima a maxima v poli [2, 1]: ");
    int array2[2] = {2, 1};
    ret = minMaxSearchRecursive(array2, 0, 1);
    if (ret.min == 1 && ret.max == 2) {
        printf("OK\n");
    } else {
        printf("NOK, v poli [2, 1] je min 1 a max 2,"),
        printf(" vracite (%d, %d) != (1, 2)\n", ret.min, ret.max);
    }


    printf("Test 18. rekurzivni vyhledavani minima a maxima v poli [0..99]: ");
    int array3[100];
    for (int i = 0; i < 100; ++i)
        array3[i] = (int) i;


    ret = minMaxSearchRecursive(array3, 0, 99);
    if (ret.min == 0 && ret.max == 99) {
        printf("OK\n");
    } else {
        printf("NOK, v poli [0..99] je min 0 a max 99,");
        printf(" vracite (%d, %d) != (0, 99)\n", ret.min, ret.max);
    }


    printf("Test 19. rekurzivni vyhledavani minima a maxima v poli nahodnych cisel: ");
    int array4[100];
    for (int i = 0; i < 100; ++i)
        array4[i] = rand() % 1000 + 1;
    array4[21] = 0;
    array4[45] = 1001;
    ret = minMaxSearchRecursive(array4, 0, 99);
    if (ret.min == 0 && ret.max == 1001) {
        printf("OK\n");
    } else {
        printf("NOK, v poli je min 0 a max 1001,");
        printf(" vracite (%d, %d) != (0, 1001)\n", ret.min, ret.max);
    }


    printf("Test 20. rekurzivni vyhledavani minima a maxima v poli nahodnych cisel (opakujicise minimum a maximum): ");
    int array5[100];
    for (int i = 0; i < 100; ++i)
        array5[i] = rand() % 1000 + 1;
    array5[21] = 0;
    array5[61] = 0;
    array5[42] = 1001;
    array5[45] = 1001;
    ret = minMaxSearchRecursive(array5, 0, 99);
    if (ret.min == 0 && ret.max == 1001) {
        printf("OK\n");
    } else {
        printf("NOK, v poli je min 0 a max 1001,");
        printf(" vracite (%d, %d) != (0, 1001)\n", ret.min, ret.max);
    }
}

> minMaxSearchRecursive(array, left, halfString);
> minMaxSearchRecursive(array, halfString + 1, right);
Both of these return a Tuple (which you need to do something with).
Say store in local variables.

Then you choose which one to return.

Tuple a = minMaxSearchRecursive(array, left, halfString);
Tuple b = minMaxSearchRecursive(array, halfString + 1, right);

Now do something to do either
return a;

or
return b;

What else do you want?

You need to create a new Tuple out of the two return results.

It doesn't seem that hard to do, if you've done the rest for yourself.

So what about this, for half an answer?
min(a.min,b.min)