C++STL中的二分查找函数

前传

以前遇到二分答案的题目时都是手写二分,但关于一些左右区间、返回值等,错误还是比较多的,最近我在网络上发现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谢谢啦

赞助

微信

C++STL中的二分查找函数

C++STL中的二分查找函数

上一篇:Cloudflare的HTML解析历史(中)


下一篇:IDEA集成docker插件实现SpringBoot项目一键部署