分治法篇：卷一：最简单的分治法应用例子

2023年4月25日，周二早上。

我想从最简单的分治法应用例子开始，而不是从经典的例子开始。

用分治法求解数组中的最大值

纯享版

#include <iostream>
using namespace std;

int getMax(int arr[], int start, int end) {
    if (start == end) {
        return arr[start];
    } else {
        int mid = (start + end) / 2;
        int max1 = getMax(arr, start, mid);
        int max2 = getMax(arr, mid+1, end);
        return max(max1, max2);
    }
}

int main() {
    int arr[] = {5, 6, 1, 2, 9, 4, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max= getMax(arr, 0, n-1);
    cout << "数组中最大值为：" << max<< endl;
    return 0;
}

博主分析版

#include <iostream>
using namespace std;

int getMax(int arr[], int start, int end) {
	//如果查找范围缩小成了一个数，就直接返回这个数
    if (start == end) {
        return arr[start];
    }
	//否则，就找到数组的中点，
	//然后分别找出从数组最左边到中点（包括中点）这段范围的最大值，
	//和从数组最右边到中点（不包括中点）这段范围的最大值，
	//最后，比较这两段范围的两个最大值，返回较大者。 
	else {
        int mid = (start + end) / 2;
        //可是，关键在于进入递归后发生了什么事情。
		//欲知进入递归后发生什么，请继续看博客的下文
        int max1 = getMax(arr, start, mid);
        int max2 = getMax(arr, mid+1, end);
        return max(max1, max2);
    }
}

int main() {
    int arr[] = {5, 6, 1, 2, 9, 4, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max= getMax(arr, 0, n-1);
    cout << "数组中最大值为：" << max<< endl;
    return 0;
}

进入递归后，到底发什么了什么事情呢？

给代码添加监视语句，可以清楚地看到整个递归过程

#include <iostream>
using namespace std;

int getMax(int arr[], int start, int end) {
    if (start == end) {
    	cout<<start<<"=="<<end<<";"<<"return "<<arr[start]<<endl;
        return arr[start];
    }
	else {
        int mid = (start + end) / 2;
        cout<<"max1=getMax(arr,"<<start<<","<<mid<<");"<<endl;
        int max1 = getMax(arr, start, mid);
        cout<<"max2=getMax(arr,"<<mid+1<<","<<end<<");"<<endl;
        int max2 = getMax(arr, mid+1, end);
        cout<<"return max(max1,max2);max("<<max1<<","<<max2<<")="<<max(max1,max2)<<endl;
        return max(max1, max2);
    }
}

int main() {
    int arr[] = {5, 6, 1, 2, 9, 4, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max= getMax(arr, 0, n-1);
    cout << "数组中最大值为：" << max<< endl;
    return 0;
}

从控制台反应的结果来看，在递归的过程中，长度为7的数组被分成了7个部分

然后这7个部分，进行了6次比较，并在比较的过程中合并成最后的结果