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