Question

分治算法求数组中最大元素位置的算法：

#include <iostream>
int Max(int a[], int low, int high);

void main()
{
int a[10], m;
for(int i=0;i<10;i++)
scanf("%d", &a[i]);
m=Max(a, 0, 9);
printf("%d\n", m);

}
/*********************************************************************************
*分治算法求数组中最大元素算法，注意：若数组有n个元素,high=n-1,*
*否则运行结果不正确，谨记数组下标从0开始。 *
*********************************************************************************/
int Max(int a[], int low, int high)
{
int mid, max, max1, max2;
if(low==high)
return low;
else
{
mid=(low+high)/2;
max1=Max(a, low, mid);
max2=Max(a, mid+1, high);
max=a[max1]>a[max2]?max1: max2;
return max;
}
}

//运行结果：
//1 9 5 6 3 7 8 4 2 0
//1
//Press any key to continue

代码是这个，但是我搞不清楚这个原理是什么

Answer 1

实质就是递归，思想是分治
max1=Max(a, low, mid);
max2=Max(a, mid+1, high);
以上把代码就是把数组分成两部分，然后这两部分中再往下分，直至if(low==high)
时返回下标，然后在每一层进行比较max=a[max1]>a[max2]?max1: max2; 把最大值的下标赋给max。
最后返回。