#STL中的二分 STL中有专门的库来处理对应的二分方法。
（1）upper_bound:函数用法为：upper_bound(arr,arr+n,x)-arr; 可以查找到第一个大于x的值的元素的位置，arr是查找范围的数组名称；
（2）lower_bound():查找第一个等于或者大于x的元素的位置
此外还有其他用法：
- 查找最后一个小于x的元素：lower_bound的前一个
- 查找第一个大于x的元素：upper_bound()自身
- 查找单调序列中x出现的次数：upper_bound()-lower_bound()
#整数二分
二分一共有两套模板，这里一一介绍。
二分的本质是在有一定顺序（不一定升序或降序）的序列中查找一个边界位置。
当我们所求的位置的要求是，在这个边界右边的区间（包含这个边界）都满足条件，在这个左边的边界的区间都不满足条件，可用第一套模板。例如在下图中：
![[Pasted image 20230731155542.png]]
白色为我们所要求的数轴区间。如果我们的要求中右边绿色区间都满足条件，那么可得： 当判断条件为true，mid同样有可能是答案，搜索区间更新为 [ l, mid ]； 而如果不满足条件，则mid在左边，那么区间更新为[mid+1, r]； 这就是第一套模板。
同样的，当我们的条件是查找在这个边界左边区间中都满足条件（包含这个边界），而右边区间都不满足时，又可得： 当判断条件为true，则mid满足条件，区间更新为[mid, r]; 如果判断条件为false，则mid在右边，区间更新为[l, mid-1 ]；
注意如果使用第二套模板（查找满足左区间条件的）则最初的mid定义为l+r+1>>1；相反的，第一套模板定义为l+r>>1；
第一套模板：
在一个序列中查找第一次出现x的下标。
易得，在这个边界的右半区间都满足的条件是：>=x。
//此处省略其他内容
l=0;
r=n-1;
mid=l+r>>1;
while(l<r)
{
if(arr[mid]>=x)
{
r=mid;
}
else
l=mid+1;
}
if(arr[l]==x)
{
return l;
}
else
return -1;
// 此处省略其他内容
第二套模板：
在一个序列中查找最后一次x出现的下标。
易得，在这个区间的左半部分满足的条件是<=x。用第二套模板。
//此处省略其他内容
l=0;
r=n-1;
mid=l+r>>1;
while(l<r)
{
if(arr[mid]<=x)
{
l=mid;
}
else
r=mid-1;
}
if(arr[l]==x)
{
return l;
}
else
return -1;
// 此处省略其他内容
例题：
# include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll q;
ll arr[100005];
int main (void)
{
scanf("%d",&n);
scanf("%d",&q);
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
while(q--)
{
ll x;
scanf("%d",&x);
ll l=0;
ll r=n-1;
ll mid;
while(l<r)
{
mid=l+r>>1;
if(arr[mid]>=x)
{
r=mid;
}
else
l=mid+1;
}
if(arr[l]!=x)
{
cout<<"-1 -1"<<endl;
continue;
}
else
cout<<l<<" ";
l=0;
r=n-1;
while(l<r)
{
mid=l+r+1>>1;
if(arr[mid]<=x)
{
l=mid;
}
else
r=mid-1;
}
cout<<l<<endl;
}
}
#浮点数二分
相较于整数，浮点数二分非常简单，无需考虑整除问题，因此左边界与右边界与mid的更新都可以直接进行。
# include<bits/stdc++.h>
# include<iomanip>
using namespace std;
typedef long long ll;
typedef long double ld;
int main (void)
{
ld n;
cin>>n;
ld l=-10000;
ld r=10000;
ld mid=(l+r)/2;
while(r-l>1e-8)
{
mid=(l+r)/2;
if(mid*mid*mid>=n)
{
r=mid;
}
else
l=mid;
}
cout<<fixed<<setprecision(6)<<l<<endl;
}