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

「爱情、让人受尽委屈。」 2022-02-24 04:52 132阅读 0赞

## 首先数组必须是有序的！ ##

## 1.binary\_search()（查找某个值在数组中是否存在） ##

使用方法：binary\_search(list,list+n,a)

list为数组，a为要查询的值,n为数组大小

binary\_search返回的是真假值，就是它只判断这个数组中是否存在这个数；

代码：

/*
    
    */
    #include<map>
    #include<set>
    #include <vector>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    const int maxn=1e4+10;
    const double pi=acos(-1.0);
    const int N=201;
    const int mod=1e9+7;
    int b[]={1,2,3,4,5,6,7,8};
    int main()
    {
        int a;
        cin>>a;
        bool s=binary_search(b,b+8,a);
        cout<<s<<endl;
        return 0;
    }

![201904030948520.png][]

如果我们想要查找它的位置该怎么办？？

使用 **lower\_bound和upper\_bound，第一个是找到第一个大于等于要查找的数的位置，第二个是找到大于要查找的数的位置**

**两者结合使用便可以得到想要的结果了**

## **2.** **lower\_bound查找第一个大于或等于某个元素的位置** ##

**使用方法：lower\_bound(list,list+n,a)**

**list为数组，n为数组大小，a为要查询的值**

### **注意事项：lower\_bound()返回的是指针，所以**所以减去数组的指针就是int变量了 ###

当查询到值存在时，返回的是第一个大于等于查询值的下标，注意是下标（0-n）

当查询值不存在且所有的值均大于要查询的值，返回0，

当查询的值不存在且所有值均小于要查询的值时，返回最后一个元素的下一个元素下标

代码：

/*
    
    */
    #include<map>
    #include<set>
    #include <vector>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    const int maxn=1e4+10;
    const double pi=acos(-1.0);
    const int N=201;
    const int mod=1e9+7;
    int b[]={2,3,6,9,11,22,32,78};
    int main()
    {
        int a;
        cin>>a;
        int index=lower_bound(b,b+8,a)-b;
        cout<<index<<endl;
        return 0;
    }

![20190403100701415.png][]![20190403100721242.png][]![20190403100737814.png][]

## 3.upper\_bound**查找第一个大于某个元素的位置。** ##

**使用方法同上**

代码同上稍微改改就行了

当两者相减的时候，便可以的得到等于查询值的元素的数的个数

代码：

/*
    
    */
    #include<map>
    #include<set>
    #include <vector>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    const int maxn=1e4+10;
    const double pi=acos(-1.0);
    const int N=201;
    const int mod=1e9+7;
    int b[]={2,3,6,9,11,11,11,22,32,78};
    int main()
    {
        int a;
        cin>>a;
        int index=upper_bound(b,b+10,a)-lower_bound(b,b+10,a);
        cout<<index<<endl;
        return 0;
    }

![20190403101303337.png][]

[201904030948520.png]: /images/20220224/6aa44f04fd3e4579a57e05d878075eb0.png
[20190403100701415.png]: https://img-blog.csdnimg.cn/20190403100701415.png
[20190403100721242.png]: https://img-blog.csdnimg.cn/20190403100721242.png
[20190403100737814.png]: /images/20220224/4bab0481e70c4283ac98d306468a6f59.png
[20190403101303337.png]: /images/20220224/bbd49aa7a3aa4907be3a2ab8a1875c89.png