分治思想的应用之——二分法

分治算法是一种很常用的思想，当你遇到大问题的时候，你可能无从下手，那么我们就可以想想问题能不能用分治法解决呢？
应用分治法必须需要满足两个条件：
（1）一个大问题它能分解成若干个独立的子问题
（2）每个子问题的求解过程都和大问题相似

当满足条件的时候，我们就可以试着用分治算法解决问题

在分治算法中有一种分支叫二分法，顾名思义，就是将问题一分为二，然后在分的算法。应用很广泛，譬如折半查找，它的时间效率比起正常的算法要高许多。

举例说明二分法：
求一个集合中最大值，和最小值；
思路 ：正常想法，先排序，再求。可以，但要是集合很大，那么效率就成问题了
下面我们来看看用二分法实现的代码：（C++）
#include"stdio.h"
#define MAXLEN 10000

int a[MAXLEN];
int main()
{
    int i,fmax=0,fmin=0;
    void mini(int i,int j,int &fmaxx,int &fminx);//二分分治
    for(i=0;i<10000;i++)
    {
        a[i]=i;
    }


    mini(0,9999,fmax,fmin);

    printf("max %d min %d",fmax,fmin);

    return 0;
}


void mini(int i,int j,int &fmaxx,int &fminx)
{
    int mid,lmax,lmin,rmax,rmin;
    if(i==j)
    {
        fmaxx=a[i];
        fminx=a[j];
    }
    else if(i+1==j)
    {
        if(a[i]<a[j])
        {
            fmaxx=a[j];
            fminx=a[i];
        }
        else
        {
            fmaxx=a[i];
            fminx=a[j];
        }
    }
//结束条件
    else
    {
        mid=(i+j)/2;
        mini(i,mid,lmax,lmin);
//左半部边
       mini(mid+1,j,rmax,rmin);
//右半部分      
        if(lmin>rmin)
            fminx=rmin;
        else
            fminx=lmin;
        if(lmax<rmax)
            fmaxx=rmax;
        else
            fmaxx=lmax;
    }
}