二分算法

转载：https://www.cnblogs.com/c1299401227/p/5517752.html
二分，分段是答案所在的区间，直接在答案所在区中分，并判断是不是答案，时间复杂度NlogN。(N是判断时间)。

二分答案：

如果已知候选答案的范围[min,max]，有时候我们不必通过计算得到答案，只需在此范围内应用“二分”的过程，逐渐靠近答案（最后，得到答案）！

一、何时可以使用“二分答案”

不是任何题目都适合使用“二分答案”的，一般有以下的一些特征：
A. 候选答案必须是离散的 ，且已知答案的范围是：[最小值min, 最大值max] （连续区间上不能进行二分操作）
    例如，在题目“Kth Largest 第k大的数”中 ==> 答案是闭区间[a[1]b[1], a[n]b[n]]上的正整数
    例如，在题目“Drying 烘干衣服”中 ==> 烘干时间t∈[0,maxT], maxT=max{a[i]}

B. 候选答案在区间[min,max]上某种属性一类一类的排列 （这样就能在此属性上进行二分操作 ），各个类别不交错混杂
    例如，在题目“Kth Largest 第k大的数”中 ==>
             （候选答案）第k大的数的值：              a[1]b[1],  ... , a[n]b[n]
             （属性分类）>这个乘积的数有多少：      n^2-1     ...      0
    例如，在题目“Drying 烘干衣服”中 ==>
             （候选答案）烘干时间：  t=0,  t=1,  t=2,  t=3,  ...,  t=maxT-1,  t=maxT
             （属性分类）能否烘干：  不能  不能   不能   能     ...    能               能
C. 容易判断某个点 是否为答案（即二分过程中，mid指向的点是否为答案）
    例如，在题目“Kth Largest 第k大的数”中 ==> λ∈[ a[1]b[1], a[n]b[n] ]
             对于某个候选答案，如果“>λ的乘积个数<k”   && “>λ-1的乘积个数≥k” ，则答案为λ
    例如，在题目“Drying 烘干衣服”中 ==>
             需要寻找第一个出现的“能”(true)，即如果check(mid-1)==false && check(mid)==true ，则答案为mid.