前传

以前遇到二分答案的题目时都是手写二分，但关于一些左右区间、返回值等，错误还是比较多的，最近我在网络上发现STL中的二分函数实属方便快捷，于是我便总结了STL库中的二分函数，供大家学习参考。

binary_search函数

功能：查找某个元素是否出现

函数模板：binary_search(a[ ],a[ ]+size,num)

参数说明：

a[ ]:数组首地址
size:数组长度
num:所要查找的数字 

返回值 ：若num存在返回true,反之，返回false

注意：要求序列有序

例题1

题目：给定一个长度为n的序列a，查找x是否在序列中 （要求用二分）####

输入描述：第一行 输入n,x

接下来一行 输入序列a

输出描述：x存在输出"true",反之输出"false"

#include<bits/stdc++.h>//万能头额文件
#include <algorithm>//该函数头文件
//两个皆可
using namespace std;
const int N=1e7+7;
int n,x;
int a[N];
int main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n)//将序列a的元素从小到大排序
    if(!binary_search(a+1,a+1+n,x))
        cout<<"false";
    else
        cout<<"true";
    return 0;
}

lower_bound函数

功能：查找第一个大于或等于某个元素的位置

函数模板：lower_bound(a[ ],a[ ]+size,num)

参数说明：

a[ ]:数组首地址
size:数组长度
num:所要查找的数字 

返回值 ：第一个大于或等于num的元素的位置

注意：是在前闭后开的区间进行二分查找，且要求序列有序，若该元素不存在，则返回值大于最后一个元素的位置

例题2

题目：给定一个长度为n从小到大排序的序列a，查找第一个大于或等于x的元素的位置

输入描述：第一行 输入n,x

接下来一行 输入序列a

输出描述：若该元素存在输出该元素的位置,反之输出-1

#include<bits/stdc++.h>//万能头额文件
#include <algorithm>//该函数头文件
//两个皆可
using namespace std;
const int N=1e7+7;
int n,x;
int a[N];
int main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int ans=lower_bound(a+1,a+1+n,x)-a;
    if(ans<=n)//若该元素存在
        cout<<ans;
    else
        cout<<-1;
    return 0;
}

upper_bound函数

功能：查找第一个大于某个元素的位置

函数模板：upper_bound(a[ ],a[ ]+size,num)

参数说明：

a[ ]:数组首地址
size:数组长度
num:所要查找的数字 

返回值 ：第一个大于num的元素的位置

注意：是在前闭后开的区间进行二分查找，且要求序列有序，若该元素不存在，则返回值大于最后一个元素的位置

例题3

题目：给定一个长度为n从小到大排序的序列a，查找第一个大于x的元素的位置

输入描述：第一行 输入n,x

接下来一行 输入序列a

输出描述：若该元素存在输出该元素的位置,反之输出-1

#include<bits/stdc++.h>//万能头额文件
#include <algorithm>//该函数头文件
//两个皆可
using namespace std;
const int N=1e7+7;
int n,x;
int a[N];
int main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int ans=upper_bound(a+1,a+1+n,x)-a;
    if(ans<=n)//若该元素存在
        cout<<ans;
    else
        cout<<-1;
    return 0;
}

后记

好了，关于C++STL中的二分查找函数我就讲到这里了，希望对大家有所帮助

如果有什么问题或需要改进的可以在下方评论区留言

另外，这是本蒟蒻第一篇真正的博客，要记得点赞+收藏+关注欧

也希望大家可以 赞助 一下 Thanks(°∀°)=3谢谢啦

赞助

微信