首页 > 代码库 > 二分算法模板
二分算法模板
二分算法求最值，掌握了算法的本质和模板，主要就是答案验证过程，验证过程经常使用贪心算法。
关键是根据题目要求设立命题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)的最小值。
1 //返回满足条件check(x)成立的最小的x. 2 function find1:longint; 3 var l,r,mid:longint; 4 begin 5 l:=1; r:=n; 6 while l<r do 7 begin 8 mid:=(l+r) div 2; 9 if check(mid) then r:=mid10 else l:=mid+1;11 end; //l=r12 exit(l);13 end;
模板二：求满足条件check(mid)的最大值。
1 //返回满足条件check(x)成立的最大的x。 2 function find2:longint; 3 var l,r,mid:longint; 4 begin 5 l:=1; r:=n; 6 while l<r do 7 begin 8 mid:=(l+r+1) div 2; 9 if check(mid) then l:=mid10 else r:=mid-1;11 end; //l=r12 exit(l);13 end;
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。