首页 > 编程语言 > 详细

三.二分算法

时间:2021-01-22 17:04:51      阅读:25      评论:0      收藏:0      [点我收藏+]

二分算法一般可以达到logn的时间复杂度,

一般二分算法进行是在有序的一段序列中,

比如0 2 5 6 8 9 16 19 24

你想找到第一个大于等于9的数,你可以先取这个数列中的中间值,即处于中间的值8

判断这个值是否大于等于9,如果小于 则在这个数的右边找,否则在其左边找,

不断缩小区间范围,最后 可以锁定16.

int a[10]={0,2,3,5,6,8,10,23,33,44};
    int n=10;
    int l=0,r=9;//l代表left即最左边的索引,r同理
    while(l<r){
        int mid=(r+l)/2;
        printf("l:%d r:%d mid=%d\n",l,r,mid);
        if(a[mid]>=11) r=mid;
        else l=mid+1; 
    } 
    cout<<a[r]<<endl;
//找到第一个小于15的值 
    int a[10]={0,2,3,5,6,8,10,23,33,44};
    int n=10;
    int l=0,r=9;//l代表left即最左边的索引,r同理
    while(l<r){
        int mid=(r+l+1)/2;
        printf("l:%d r:%d mid=%d\n",l,r,mid);
        if(a[mid]<15) l=mid;
        else r=mid-1; 
    } 
    cout<<a[r]<<endl;

模板的差别

l=mid时,mid=(r+l+1)/2;r=mid-1;//不加1在某些数据中会陷入死循环

r=mid时,mid=(r+l)/2;l=mid+1;

C++STL中有现成的lower_bound和upper_bound可以用来实现二分查找

序列必须是有序序列

upper_bound()返回的是被查序列中第一个大于查找值的指针;

lower_bound()返回的是被查序列中第一个大于等于查找值的指针;

int t=upper_bound(a+l,a+r,m)-a

int t=lower_bound(a+l,a+r,m)-a

解释:在升序排列的a数组内二分查找[l,r]区间内的值为m的元素。返回m在数组中的下标。

特殊情况:

1.如果m在区间中没有出现过那么返回第一个比m大的数的下标。2.如果m比所有区间内的数都大,那么返回r。这个时候会越界,小心。3.如果区间内有多个相同的m,返回第一个m的下标。

以下为浮点数的二分法

例题

Now,given the equation 8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == Y,can you find its solution between 0 and 100;
Now please try your lucky.

InputThe first line of the input contains an integer T(1<=T<=100) which means the number of test cases. Then T lines follow, each line has a real number Y (fabs(Y) <= 1e10);OutputFor each test case, you should just output one real number(accurate up to 4 decimal places),which is the solution of the equation,or “No solution!”,if there is no solution for the equation between 0 and 100.Sample Input

2
100
-4

Sample Output

1.6152
No solution!


答案

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std; 
const int MAXN=1e5+10;
const double eps=1e-8;
double p[MAXN];
int a,b;
#define pi acos(-1.0) 
double fanhui(double x)
{
	return 8*pow(x,4)+7*pow(x,3)+2*pow(x,2)+3*x+6;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>a;
//		for(int i=1;i<=a;i++)
//			scanf("%lf",&p[i]);
//		sort(p+1,p+1+a);
		double l=0,r=100;
//		double ans=0;
//		int e=1000; 
		double mid=(l+r)/2;
		if(a<fanhui(0)||a>fanhui(100))
		{
			cout<<"No solution!"<<endl;
		}
		else {
		
		while(l+eps<=r) //此处还有另一种写法 设置 循环次数 int e=200 while(e--) 
		{
			mid=(l+r)/2;
			if(fanhui(mid)==a)
			{
				return mid;
			}
			else if(fanhui(mid)<a)
			{
				l=mid;
			}
			else if(fanhui(mid)>a)
			{
				r=mid;
			}
			
		}
		printf("%.4f\n",mid);
		} 
		 
	} 
}

  

三.二分算法

原文:https://www.cnblogs.com/BlogBaudelaire/p/14313255.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!