文章目录
- 1、整数集合上的二分
- 2、实数域上的二分
- 3、三分求单峰函数极值
- 4、二分答案转化为判定
二分的基础用法是在单调序列或单调函数中进行查找。因此，当问题的答案具有单调性时，就可以通过二分把求解转化为判定（根据复杂度理论，判定的难度小于求解），这使得二分的运用范围变得很广泛。进一步地，还可以扩展到通过三分法去解决单峰函数的极值以及相关问题。
对于整数域上的二分，需要注意终止边界、左右区间取舍时的开闭情况，避免漏掉答案或造成死循环；对于实数域上的二分，需要注意精度问题。
1、整数集合上的二分
本文所使用的二分写法保证最终答案处于闭区间 [ l , r ] [l, r]
