sundeepblue
4/21/2014 - 3:00 PM

finds the minimum and maximum values within an unsorted array using divide-and-conquer

finds the minimum and maximum values within an unsorted array using divide-and-conquer

void dc(int A[], int N, int low, int high, int &minv, int &maxv) {
    if(low > high) return;
    if(low == high)
        minv = maxv = A[low];
    else {
        int mid = (low + high) >> 1;
        int minv1 = INT_MAX, maxv1 = INT_MIN, minv2 = INT_MAX, maxv2 = INT_MIN;
        dc(A, N, low, mid, minv1, maxv1);
        dc(A, N, mid+1, high, minv2, maxv2);
        minv = min(minv1, minv2);
        maxv = max(maxv1, maxv2);
    }
}

void get_min_max(int A[], int N) {
    int minv = INT_MAX, maxv = INT_MIN;
    dc(A, N, 0, N-1, minv, maxv);
    cout << minv << ", " << maxv << endl;
}