二分算法模板

二分算法求最值，掌握了算法的本质和模板，主要就是答案验证过程，验证过程经常使用贪心算法。

关键是根据题目要求设立命题check(x)。

验证答案mid：

Check(mid):是否成立？

求满足条件Check(mid)的最小值：

–if  check(mid) then r:=mid else l:=mid+1;

求满足条件Check(mid)的最大值：

–if  check(mid) then l:=mid else r:=mid-1;

模板一：求满足条件check(mid)的最小值。

//返回满足条件check(x)成立的最小的x.
function find1:longint;
    var l,r,mid:longint;
    begin
      l:=1; r:=n;
      while l<r do
        begin
          mid:=(l+r) div 2;
          if check(mid) then r:=mid
          else l:=mid+1;
        end; //l=r
      exit(l);
    end;

模板二：求满足条件check(mid)的最大值。

//返回满足条件check(x)成立的最大的x。
 function find2:longint;
    var l,r,mid:longint;
    begin
      l:=1; r:=n;
      while l<r do
        begin
          mid:=(l+r+1) div 2;
          if check(mid) then l:=mid
          else r:=mid-1;
        end; //l=r
      exit(l);
    end;