二分法
:即一分为二的方法,对于数据较多时(前提是已经排好序的数据)进行查找,可以根据条件判断直接将搜索区域减少一半,可以根据区间划分分为整数二分
和浮点数二分
浮点数二分
:不必考虑划分区间边界的问题,只需要保证精度满足要求即可
思路示例
:
double bsearch_3(double l, double r)
{
// eps 表示精度,取决于题目对精度的要求
const double eps = 1e-6;
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
举例:数的三次方根
代码实现【题目描述】
给定一个浮点数,求它的三次方根
【输入格式】
共一行,包含一个浮点数n
【输出格式】
共一行,包含一个浮点数,表示问题的解
注意:结果保留6位小数
【数据范围】
−10000 ≤ n ≤ 10000
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
double x = sc.nextDouble();
double l = -10000, r = 10000;
while(r - l > 1e-8){
double mid = (l + r) / 2;
if(mid * mid * mid >= x) r = mid;
else l = mid;
}
//直接通过c语言的输出格式规定精度
System.out.printf("%.6f", l);
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)