stl 二分容器小总结

待我称王封你为后i 2022-02-25 09:08 237阅读 0赞

### stl大法好 ###

stl二分常用的有三个容器。  
分别介绍一下：  
upper\_lound(数组首地址，数组尾地址，查找的数A)；  
lower\_lound(数组首地址，数组尾地址，查找的数A）;

这两个容器返回值都是地址。

upper\_lound的返回值是数组里面第一个大于A的那个位置的地址。  
lower\_lound的返回值是数组里面第一个大于等于A的那个位置的地址。  
注:  
返回值都是地址。如果想要那个位置的下标。则可以将返回的地址减去数组首地址即可以得到。并且这两个容器的用途都是用于非递减的数组中。

还有一个查找数A在数组中是否出现过的容器。  
binary\_search(数组首地址,数组尾地址,查找的数A);  
如果要查找的数A在数组中，则这个容器返回1；  
如果要查找的数不在数组中，则这个容器返回0；

上面介绍的都是在数组是非递减的情况下。  
那么如果我们是要在非递增数组中使用呢？  
1，重载。  
2，容器其实默认的是有4个参数的，省掉第四个参数（即默认为非递减序列）  
如果将第四个参数加上，则这些容器可在非递增序列使用(同时大于变小于，大于等于变小于等于)。  
格式：  
upper\_lound(数组首地址，数组尾地址，查找的数A，greater () )；  
具体代码：

#include"string.h"
    #include"functional"
    #include"iostream"
    #include"algorithm"
       using namespace std;
    typedef long long ll;
    #define scanll(a,b) scanf("%I64d%I64d",&a,&b);
    #define scanl(a) scanf("%I64d",&a);
    #define scanff(a,b) scanf("%lf%lf",&a,&b);
    #define scan1f(a) scanf("%lf",&a);
    #define prinll(a,b) printf("%I64d %I64d",a,b);
    #define prinl(a) printf("%I64d",a);
    #define printff(a,b) printf("%lf %lf",a,b);
    #define printlf(a) printf("%lf",a);
    int main()
    {
        int a[100]={4,10,11,30,30,69,70,96,100};
        int a1[100]={100,96,70,69,30,30,11,10,4};
        int binary1=binary_search(a,a+9,70);
        printf("binary1=%d\n",binary1);
        int binary2=binary_search(a1,a1+9,70,greater<int> ());
        printf("binary2=%d\n",binary2);
        
        int ans=lower_bound(a,a+9,30)-a;
        printf("ans=%d\n",ans);
        int loc=lower_bound(a1,a1+9,30,greater <int> () )-a1;
        printf("loc=%d\n",loc);
        
        int pos=upper_bound(a,a+9,30)-a;
        printf("pos=%d\n",pos);
        int id=upper_bound(a1,a1+9,4,greater<int> () )-a1;
        printf("id=%d\n",id);
        
    }

参考博客：[https://blog.csdn.net/xzymmd/article/details/83902281][https_blog.csdn.net_xzymmd_article_details_83902281]

[https_blog.csdn.net_xzymmd_article_details_83902281]: https://blog.csdn.net/xzymmd/article/details/83902281