二分法：
在看这个视频前，我对于二分法是一头雾水的，又加上这个算法我个人很容易写错emm...。视频提到ACwing上的一道题，我用自以为聪明的方法去做，结果TLE了，实在丢人，不说了，开整！
对于例题 789：数的范围，寻找一个数前后第一次与最后一次出现的坐标。我们需要这个模板：
数组定为number[];
（1）来看第一种情况：如图，假设两个点分别是最先与最后出现的位置。求第一次x出现的位置实际上就是（1）这种情况。那么我们定一个条件
mid=(l+r)>>1 if(number[mid]在a中)
r=mid; 区间变为[L,mid], 因为mid处可能是答案，所以mid不要加一也不要减一。
else(落在b中)
l=mid+1; 区间变为[mid+1,R]
（2）来看第二种情况：如图，就是求x最后一次出现的位置了。依然是
int mid=(l+r+1)>>1; if(number[mid]在b中)
l=mid 区间变为[mid,R]，mid不要动因为mid处可能是答案
else
r=mid-1 因为mid处肯定不是答案，所以要减一，区间变为[L,mid-1]；
但是注意要注意（2）中的(L+r+1)>>1,因为如果 l=r-1时，式子不加一会出现mid=L+1/2,因为向下取整，所以mid=L,进入if后会一直求出区间[L,R]造成死循环，而(1)就不会出现。
综上，有以下两个模板，分别对应不同的情况
//区间[L,R]被分成[L,mid]和[mid+1,R]时
int bsearch_1(int l,int r)
{
while(l<r)
{
int mid=l+r >>;
if(check(mid))
r=mid;
else
l=mid+;
} }
//区间[L,R]被分成[L,mid-1]和[mid,R]时
int bsearch_2(int l,int r)
{
while(l<r)
{
int mid=l+r+ >>;
if(check(mid))
l=mid;
else
r=mid-; }
}
然后上789代码 ：
#include<iostream>
const int maxn=1e5+;
using namespace std; int a[maxn];
int n,k;
int main()
{
cin>>n>>k;
for(int i=;i<n;i++)
cin>>a[i];
while(k--)
{
int x;
cin>>x;
int l=,r=n-;
while(l<r)
{
int mid=(l+r)>>;
if(a[mid]>=x)
{
r=mid;
}
else
{
l=mid+;
}
}
if(a[l]!=x)
cout<<"-1 -1"<<endl;
else
{
cout<<l<<' ';
int l=,r=n-;
while(l<r)
{
int mid=(l+r+)>>;
if(a[mid]<=x)
{
l=mid;
}
else
r=mid-;
}
cout<<r<<endl;
}
}
}
再来个手动开方嘿嘿，二分法：
#include<iostream>
using namespace std;
#include<cstdio>
int main()
{
double x;
while(cin>>x)
{
double l=,r=x;
while((r-l)>1e-)//精度不够再加，可以时1e-8
{
double mid=(l+r)/;
if(mid*mid>x)
r=mid;
else
l=mid;
}
printf("%lf\n",l);
}
}
开三次方：ACWING 790
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
double x;
while(cin>>x)
{
double l,r;
if(x>=)
l=,r=x;
else
l=x,r=;
while(fabs(r-l)>1e-)
{
double mid = (l+r)/;
if(mid*mid*mid>x)
r=mid;
else
l=mid;
}
printf("%lf\n",l);
}
}