3. 二分
3.1 整数二分
3.1.1 思想
二分的本质并不是单调性:有单调性一定可以二分,可以二分不一定有单调性。
如果可以找到一个性质,将区间分为一边满足,一边不满足,那么二分就可以寻找这个性质的边界。
每次分一半,保证答案处在目标区间里。二分一定会有解。
3.1.2 模板
1 | //目标在右区间。区间[l, r]被划分成[l, mid], [mid+1, r] |
3.1.3 例题
- 给定一长度为n的升序数组,以及q个查询。对于每次查询,输入一个数k,返回元素k的起始位置和终止位置(从0开始)。不存在则返回-1 -1
1 | //测试 |
1 |
|
3.2 浮点数二分
- 更简单,不用考虑+1问题。
3.2.1 例题
- 计算一个数的平方根
1 |
|
3.3 练习
三次方根
给定一个浮点数n,求它的三次方根。
数据范围:-10000.0<=n<=10000.0
精度要求:绝对误差小于1e-6
1 |
|