用分治法寻找数组中的最大值与最小值

171 阅读 0 评论 113 点赞

我是靠谱客的博主甜甜月饼，这篇文章主要介绍用分治法寻找数组中的最大值与最小值，现在分享给大家，希望可以做个参考。

整体思路：
将数组划分成两半，分别找出两边的最小值与最大值，两边局部最小值中较小的那个为整体最小值，两边局部最大值中较大的为整体的最大值

由于是递归实现需要考虑终止条件：当区间容量为2或1时，获取局部最小值与最大值

void getMaxMin(vector<int> &a, int left, int right, int &min, int &max)
{
int max1, max2, min1, min2;
if(right - left == 1 || right == left)
{
min = a[right] <= a[left] ? a[right] : a[left];
max = a[right] >= a[left] ? a[right] : a[left];
return;
}
int mid = (left + right) / 2;
getMaxMin(a, left, mid, min1, max1);
getMaxMin(a, mid+1, right, min2, max2);
min = min1 < min2 ? min1 : min2;
max = max1 > max2 ? max1 : max2;
}