三.二分算法

二分算法一般可以达到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的下标。

以下为浮点数的二分法

例题

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