[算法设计与分析]4.3.5非等分分治(一组数的第二小)

#include<stdio.h>
#include<iostream>
#include<cstring>

using namespace std;

const int N = 7;

int SecondSmall(int a[], int n);
void FindTwo(int a[], int i, int j, int &fmin1, int &fmin2);

int main ()
{
    int a[N] = {2, 3, 1, 6, 5, 9, 0};
    cout << SecondSmall(a, N) << " is the second small number" << endl;
}

//利用查找最小的两个数 才可以将原问题进行分解
int SecondSmall(int a[], int n)
{
    int min1, min2;
    FindTwo(a, 0, n - 1, min1, min2);
    return min2;
}

void FindTwo(int a[], int i, int j, int &fmin1, int &fmin2)
{
    int lmin1, lmin2, rmin1, rmin2;
    int mid;

    //递归出口
    if(i == j)
        fmin2 = fmin1 = a[i];
    else if(i == j - 1)
    {
        fmin2 = a[i] > a[j] ? a[i] : a[j];//fmin2存储较大
        fmin1 = a[i] > a[j] ? a[j] : a[i];
    }
    else
    {
        mid = (i + j) / 2;
        FindTwo(a, i, mid, lmin1, lmin2);
        FindTwo(a, mid + 1, j, rmin1, rmin2);

        if(lmin1 < rmin1)
        {
            fmin1 = lmin1;
            if(lmin1 != lmin2 && lmin2 < rmin1)//此处一定要加一个判断条件 以避免递归出口为i==j的情况min1和min2的值相同
                fmin2 = lmin2;//Eg:2 3 1 则rmin1=rmin2=1 此时经过判读 则fmin1=fmin2=1 显然是错误的
                                //因此该判断取值是否相等
            else
                fmin2 = rmin1;
        }
        else
        {
            fmin1 = rmin1;
            if(rmin1 != rmin2 && rmin2 < lmin1)
                fmin2 = rmin2;
            else
                fmin2 = lmin1;
        }
    }
}