最大值最小化问题 - Bisection - binary search

Also check LeetCode 410 - Split Array Largest Sum
http://blog.csdn.net/nanjunxiao/article/details/8145971

把一个包含n个正整数的序列划分成m个连续的子序列。设第i个序列的各数之和为S(i)，求所有S(i)的最大值最小是多少？

例如序列1 2 3 2 5 4划分为3个子序列的最优方案为 1 2 3 | 2 5 | 4，其中S(1),S(2),S(3)分别为6，7，4，那么最大值为7；

如果划分为 1 2 | 3 2 | 5 4，则最大值为9，不是最小。

问题分析：

能否使m个连续子序列所有的s(i)均不超过x，则该命题成立的最小的x即为答案。该命题不难判断，只需贪心，每次尽量从左

向右尽量多划分元素即可。

我们把该问题转化为递归分治问题，类似于二分查找。首先取Sum和元素最大值的中值x，如果命题为假，那么答案比x大；

如果命题为真，则答案小于等于x。问题得解，复杂度为O（n*logSum）

bool is_part(int x)//是否能把序列划分为每个序列之和不大于x的m个子序列 
{
 //每次往右划分，划分完后，所用的划分线不大于m-1个即可
 int t=0,s=0;
 bool ok=true;
 for(int i=0;i<n;i++)
 {
  if(A[i]>x)//假如有其中一个元素大于x，则极端地把划分线分别设在在其左边和右边，都不能使这一个只有一个元素的序列之和不大于x，更不用说所有序列之和不大于x 
  {
   ok=false;
   break;
  }
  if(s+A[i]>x)//大于，不能再把当前元素加上了 
  {
   t++;//多用了一条横杠
   s=A[i];
   if(t>m-1)//t=m时退出，即在最后一个元素之前都已经用了m条划分线，此时已把序列划分成了m+1个序列，太过分了，让其适可而止 
   {
    ok=false;break;
   }
  }else
  {
   s+=A[i];//把当前元素与前面的元素连上，以便尽量往右划分，贪心到底 
  }
 }
 return ok;
}
int sum()
{
 int s=0;
 for(int i=0;i<n;i++) s+=A[i];
 return s;
}
int binary_solve()
{
 int x=max,y=sum(); 
 while(x<y)
 {
  int m=x+(y-x)/2;
  if(is_part(m)) y=m;
  else x=m+1;
 }
 return x;
}

http://blog.csdn.net/lzw_java/article/details/7486512