整数二分法:
1、确定一个区间,使得目标值在一定区间内
2、找一个判断条件:条件具有二段性(前半段满足,后半段不满足);答案是二段性的分界点,答案是左半段的终点或者右半段的起点 (多与大多数二分题)
3、判断中点m在该判断条件下是否成立,若成立,考虑答案在哪个区间,不成立,考虑答案在哪个区间
4、如果更新方式是R=m 不做处理,如果l=m,m需要+1;
模板1、红色区域的右端点(m为区间[L,R]的中点,分为两个区间[L,m-1][m,R])
如果 m在红色区域中,则红色的右端点在[m,R]中,否则 在[L,m-1]
while(L<R)
m=(L+R+1)/2 //+1的原因是将下取整变为上取整(l=m将会死循环)
if m在红(左)l=m; else r=m-1;
模板2、绿色区域的左端点(分为两个区间[L,m][m+1,R])
如果 m在绿色区域中中,说明绿色区域的左端点在[L,m]中,否则 在[m+1,R]。
while(L<R)
m=(L+R)/2
if m 在绿(右)R=m; else l=m+1