前言

        事实上，我们在解决实际问题时一般会用二分答案而不是二分查找。今天我就来给大家介绍一下二分查找这种由二分法衍生出来的办法。

程序设计思路

        相比于二分查找，二分答案有极为重要的一点不同——check思想。也就是说，每查到一个答案都将其经过特定的程序后再与基准数比较。这样看来，二分答案其实就是在二分查找的基础上加了一步检查。

        二分查找往往是在一堆数里查找答案，而二分答案则通常面对一个范围，这也是它们之间的一显著区别。

代码实现

        解方程中经常会用到二分答案，因为它的范围很广，而且往往包含浮点数答案。来看下面这题：

        这题目明摆着要我们用二分答案，否则如果用浮点数试过去效率太低，容易TLE。看代码：

#include <bits/stdc++.h>

double a,b,c,d,l,m,r;//a、b、c、d如题意，l、m、r分别为左、中、右指针

double f(double x){//检查解是否合法，算一遍方程

	return a*pow(x,3)+b*pow(x,2)+c*x+d;

}

int main(){

	scanf("%lf%lf%lf%lf",&a,&b,&c,&d);

	for(int i=-100;i<100;i++){//由题意得有200个整数区间，分别查找

		l=i;

		r=i+1;

		if(f(l)==0){//特判，正好相等时直接输出

			printf("%.2lf ",l);

			continue;

		}

		if(f(l)*f(r)>=0) continue;//用题目中所给式子判断

		while(r-l>0.001){//不断缩小范围

			m=(l+r)/2;

			if(f(l)*f(m)<=0) r=m;

			else l=m+0.001;

		}

		printf("%.2lf ",m);

	}

	return 0;

}

        代码中的f()函数就是所谓check思想。这样一来便很好理解了。

结语

        二分答案作为二分算法的一个衍生分支，能够解决很多问题。我是faryou，再见！

本文链接：https://blog.faryou.eu.org/post/101.html 转载需经作者授权！