最大值和最小值问题的最优算法_寻找最大值的最优算法

1、最大值和最小值问题的最优算法
给定n个实数存放于一维数组A中，试设计一个算法在最坏情况下用3n/2-2次的比较找出A中的最大值和最小值（为简化，可假设n为偶数）

#define inf 0x3f3f3f3f
void maxmin(int* a, int left, int right, int* max, int* min)
{
    int mid;
    int lmax = 0, lmin = inf, rmax = 0, rmin = inf;
    if (left == right)//边界条件
    {
        *max = a[left];
        *min = a[right];
        return;
    }
    //分开始递归
    mid = (left + right) / 2;
    maxmin(a, left, mid, &lmax, &lmin);
    maxmin(a, mid + 1, right, &rmax, &rmin);
    //合并
    if (lmax > rmax)
    {
        *max = lmax;
    }
    else
    {
        *max = rmax;
    }
    if (lmin < rmin)
    {
        *min = lmin;
    }
    else
    {
        *min = rmin;
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

转载于https://www.cnblogs.com/wkfvawl/p/11460280.html

1

1