分析以下程序的功能及其实现过程,写出运行结果,并为关键语句做注释。
#include
using namespace std;
int biDiv(int* p, int Lp, int Rp) {
int Lm, Rm;
if (Lp == Rp) {
return p[Lp];
}
else {
Lm = biDiv(p, Lp, (Lp + Rp) / 2);
Rm = biDiv(p, (Lp + Rp) / 2 + 1, Rp);
if (Lm > Rm) {
return Lm;
}
else {
return Rm;
}
}
}
int main()
{
int a[11] = { 1,3,-2,4,5,-1,2,4,6,0,-4 };
cout << biDiv(a, 0, 10) << endl;
return 0;
}
这是个求数组最大值的函数
采用递归方法,不断对数组进行对半分,然后在分成的两半中各自找出最大值进行比较,其中更大的值就是最大值
由于递归逻辑,所以递归到最里层就是每相邻两个元素比较大小,获得较大值,然后这些较大值再两两分组,找出较大值,如此递归
使用这个方法,算法复杂度为O(logn),当数组大小很大时,效率很高
而普通的遍历算法,算法复杂度为O(n)
二分查找法找出数组中的最大值,结果为6,关键语句就是递归调用那两行:
Lm = biDiv(p, Lp, (Lp + Rp) / 2);
(Lp + Rp) / 2就是数组p的最中间那个值的下标,递归去判断左半部分有没有最大值
Rm = biDiv(p, (Lp + Rp) / 2 + 1, Rp);
(Lp + Rp) / 2 + 1 就是数组p的最中间那个值往右的下标,递归去判断右半部分有没有最大值