二分法的模板有两个不同的使用规则
1、mid的求法根据使用的判断语句条件来判断
2、判断条件的意思是“满足这个条件的第一个数”
3、第一种使用方法(a[mid]>=x)
{
使用的是r=mid;
l=mid+1;
}
4、第二种使用方法(a[mid]<=x)
{
使用的是l=mid;
mid =l + r + 1 >> 1;
r=mid-1;
}
二分法边界问题分析:
为什么要+1:
有一种特殊情况下:l=r-1;
mid = (l+r)/2 l=mid;(l=l)
下一次循环会是同样的结果的造成死循环
为什么不需要+1;
l=r-1;
mid=(l+r)/2 r=l;(跳出循环)
不会造成死循环的
全加上+1是行不通的会造成死循环