今天开始学算法系列 -- 二分搜索的应用

    二分搜说是很实用的一个搜素算法，但是它并不一定是只在搜索指定数值的时候才有用。
   proj NO.1064这道题就可以用二分搜索很好的解决。
   关键的思想在于，像在求解最大化或最小化的问题的时候，可以想办法把条件公式求出，然后对于满足条件的值在范围内进行二分搜索来获取最后的答案，而不是直接去求解答。
    这道题可以套取公式： 求满足每根绳子的长度/x 的总和 = 指定的分割绳子数的时候x的最大值。
    对于这个条件， 我们就可以在0-INF这个范围内进行2分搜索来寻找这样的值了
    
    直接上代码：
     

//二分搜索的应用思想
// 套用公式： 定义上下界，搜索在范围内满足条件c(x)的x
#include "stdafx.h"

#define MAXN 4 //绳子的总数
#define MAXCN 2 //切割出的总数

float length[MAXN] = {8.02,7.43,4.57,5.39};
int low = 0;
int up = 10;

bool C(int mid)
{
    int k = 0;
    for (int i = 0; i < MAXN; i++)
    {
        k += length[i] / mid;
    }
    if (k == MAXCN)
        return true;
    else
    {
        if (k < MAXCN)
            up = mid;
        else
            low += mid;
    }
    return false;
}

int _tmain(int argc, _TCHAR* argv[])
{
    while (1)
    {
        int mid = (up - low) / 2;
        if (mid == 0)
        {
            printf("can't find such data\n");
            return true;
        }
        if (C(mid))
        {
            printf("The max length of pices is %d\n",mid);
            return true;
        }
    }

    return 0;
}