日常踩坑
二分模板的对称性
如果是单调递增的
求>= x的最小值 或者是单调递减的求 <= x 最大值
while(l < r)
{
int mid = l + r >> 1;
if(f[mid] >= x)r = mid;
else l = mid + 1;
}
如果是递增的求 <= x 最大值 或者是递减的求 >= x 最小值
while(l < r)
{
int mid = l + r + 1 >> 1
if(f[mid] <= x)l = mid;
else r = mid - 1;
}
这两种写法没区别吧？
同学，区别很大，我写的不明显吗？？？？
有点不太理解。。
有什么好的方法理解二分法嘛
建议自己在纸上模拟一下，二分的两个模板是考虑到边界问题的就比如我要用第一个模板，mid = l + r >> 1那么 由于 假如f函数里面就只有 两个数 a 和 b 且 a <= b 那么l = 0, r = 1 mid = 0，如果我说我这样写 if(f[mid] >= x) l = mid, 那么l = 0,死循环了， 同理第二个模板用到的是l + r + 1 >> 1 为上取整 那么 if(f[mid <= x) r = mid 也会死循环 ，这样写就是为了处理边界问题，自己模拟一下就明白啦hh
小口诀
r咪不变大最小 l咪加1小最大~~ hh可以