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

56 阅读 0 评论 37 点赞

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

概述

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

由于是递归实现需要考虑终止条件：当区间容量为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;
}