二分法

HDU-2199-Can you solve this equation

http://acm.hdu.edu.cn/showproblem.php?pid=2199

二分法求方程的根

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
double sol(double x)
{
	return 8*pow(x,4)+7*pow(x,3)+2*pow(x,2)+3*x+6;
}
int main()
{
	int t;
	double r,l,mid,y;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lf",&y);
		if(sol(0)<=y&&sol(100)>=y)
		{
			l=0;
			r=100;
			while(r-l>1e-6)
			{
				mid=(l+r)/2;
				if(sol(mid)<y)
				l=mid;
				else
				r=mid;
			}
			printf("%.4lf\n",mid);
		}
		else
		printf("No solution!\n");
	}
	return 0;
}

HDU-2141-Can you find it

http://acm.hdu.edu.cn/showproblem.php?pid=2141

二分法用于查找

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int l,n,m;
int a[505],b[505],c[505],ab[255025];
int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}
int find(int x)
{
	int low,high,mid;
	low=0;
	high=l*n-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(ab[mid]==x)
		return 1;
		if(ab[mid]>x)
		high=mid-1;
		else
		low=mid+1;
	}
	return 0;
}
int main()
{
	int i,j,k,t;
	int flag;
	int cases=1;
	while(scanf("%d%d%d",&l,&n,&m)!=EOF)
	{
		printf("Case %d:\n",cases++);
		for(i=0;i<l;i++)
		scanf("%d",&a[i]);
		for(i=0;i<n;i++)
		scanf("%d",&b[i]);
		for(i=0;i<m;i++)
		scanf("%d",&c[i]);
		for(i=0;i<l;i++)
		for(j=0;j<n;j++)   //所有a+b的和
		ab[i*n+j]=a[i]+b[j];
		qsort(ab,l*n,sizeof(ab[0]),cmp);
		scanf("%d",&t);
		while(t--)
		{
			flag=0;
			scanf("%d",&k);
			for(i=0;i<m;i++)
			if(find(k-c[i]))
			{
				flag=1;
				break;
			}
			if(flag)
			printf("YES\n");
			else
			printf("NO\n");
		}
	}
	return 0;
}