浮点二分
浮点二分比整数二分简单得多，因为无需判断边界条件，只要设置精度即可。
- 设置精度标准：一般题目要求保留x位的话，精度加上2没有大问题。
模板
1
2
3
4
5
6
7
8
9
10
11
| const double eps = 1e-9;
double binary_search(double left, double right) {
int l=left, r=right;
while (r-l > eps) {
double mid = (l+r)/2;
if(check(mid)) r = mid;
else l = mid;
}
return l;
}
|
#例题
求立方根
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<bits/stdc++.h>
using namespace std;
long long x;
const double P=1e-2;
void work(){
cin>>x;
double l=0,r=1e5+5;
while(r-l>P){
double mid=(r+l)/2;
if(mid*mid*mid<=x) l=mid;
else r=mid;
}
int ans=r;
cout<<"l: "<<l<<endl;
cout<<"r: "<<r<<endl;
cout<<ans<<endl;
}
int main(){
work();
return 0;
}
|