文档章节

有关STL的二分查找函数的理解

雅各宾
 雅各宾
发布于 2014/09/12 09:30
字数 1865
阅读 57
收藏 0

// http://blog.csdn.net/pi9nc/article/details/8717912

1、调用此4函数的基本前提:容器是“已经排序”(/sorted)的(/Sorted Container)。

2、说到“排序”,对应肯定有“排序/比较算子” (/Sort/Commpare Operator)

3、能应用此4函数的容器可以Concept描述为: (Sorted Container, Sort/Commpare Operator)

4、假定两个Concept如下:
        (Sorted1 Container, Sort1/Commpare1 Operator)
        (Sorted2 Container, Sort2/Commpare2 Operator)
    那么,如下的Concept就是错误/非法/没有意义的
        (Sorted1 Container, Sort2/Commpare2 Operator)
        (Sorted2 Container, Sort1/Commpare1 Operator)

5、案例说明(sort/commpare operator):
    譬如有乱序容器(-1,-4,-2,3,4,1,7)
        5.1 按大小升序排序得       (-4,-2,-1,1,3,4,4,7) -- 简称 ACS_CONTAINER    
        5.2 按大小降序排序得       (7,4,4,3,1,-1,-2,-4) -- 简称 DCS_CONTAINER    
        5.3 按绝对值降序排序得譬如 (7,4,-4,4,3,-2,1,-1) -- 简称 ABS_ACS_CONTAINER
        5.4 按绝对值升序排序得譬如 (-1,1,-2,3,-4,4,4,7) -- 简称 ABS_DCS_CONTAINER
        5.5 按对2求模升序排序得譬如(-2,4,-4,4,-1,1,3,7) -- 简称 MODE_ACS_CONTAINER
        ... 不一而足

6、分别说明此4函数的意义:
    6.1 container.binary_search( it_first, it_last, object, commpare_method )
        对区间container(it_first,it_last)找对象/元素object, 排序算子是commpare_method(Sort/Commpare Operator)。当然,container是已经按照commpare_method进行过排序的容器,这点在此再强调一次,往后不再累赘.
    6.2 container.lower_bound( it_first, it_last, object, commpare_method )
        对区间container(it_first,it_last)找
            针对此对象/元素object,服从排序算子是commpare_method,object该予以安排的位置s
        的第一个位置
        譬如 对
            ACS_CONTAINER
        找 1 的lower_bound 是 [3]1 -- 这里3是指base0的索引/迭代下标
        找 2 的lower_bound 是 [4]3
    6.3 container.upper_bound( it_first, it_last, object, commpare_method )
        对区间container(it_first,it_last)找
            针对此对象/元素object,服从排序算子是commpare_method,object该予以安排的位置s
        的最后一个位置
        譬如 对
            ACS_CONTAINER
        找 1 的upper_bound 是 [4]3
        找 4 的upper_bound 是 [7]7
    6.4 container.equal_range( it_first, it_last, object, commpare_method )
        对区间container(it_first,it_last)找等于也就是不大于也不小于object的前开后闭迭代区间[it1,it2)
        它的行为等价于
            template <class ForwardIterator, class T>
            pair<ForwardIterator,ForwardIterator>
            equal_range
            (ForwardIterator first, ForwardIterator last, const T& val)
            {
                ForwardIterator it = lower_bound (first,last,val);
                return make_pair ( it, upper_bound(it,last,val) );
            }
        譬如 对
            ACS_CONTAINER
        找 4 的equal_range 是 [5,7) 亦即 4,4,7

7、附测试代码如下

////////////////////////////////////////////////////////////////////////////////
// http://blog.csdn.net/pi9nc/article/details/8717912
// binary_search example
# include <iostream>     // std::cout
# include <algorithm>    // std::binary_search, std::sort
# include <vector>       // std::vector
# include <xutility>
# include <conio.h>

////////////////////////////////////////////////////////////////////////////////
bool asc_cmp(int i,int j) { return (i < j); }
bool dsc_cmp(int i,int j) { return (i > j); }

////////////////////////////////////////////////////////////////////////////////
void test_binary_seach()
{
    int myints[] ={1,2,3,4,5,4,3,2,1};
    std::vector<int> asc_v(myints,myints+9);  // 1 2 3 4 5 4 3 2 1
    std::vector<int> dsc_v=asc_v;

    std::sort(asc_v.begin(),asc_v.end()/*, asc_cmp*/);
    std::sort(dsc_v.begin(),dsc_v.end(),dsc_cmp);

    std::cout << "asc_v: ";
    for(auto& it : asc_v)
    {
        static int i = 0;
        printf( "[%d]%d ", i++, it );
    }
    std::cout << std::endl;

    std::cout << "dsc_v: ";
    for(auto& it : dsc_v)
    {
        static int i = 0;
        printf( "[%d]%d ", i++, it );
    }
    std::cout << std::endl;

    std::cout << "binary_search looking for a 3 in ^v with ^cmp... ";
    if(std::binary_search(asc_v.begin(),asc_v.end(),3))
        std::cout << "found!\n"; else std::cout << "not found.\n";

    std::cout << "binary_search looking for a 6 in ^v with ^cmp... ";
    if(std::binary_search(asc_v.begin(),asc_v.end(),6,asc_cmp))
        std::cout << "found!\n"; else std::cout << "not found.\n";

    std::cout << "binary_search looking for a 3 in ^v with Vcmp... ";
    if(std::binary_search(asc_v.begin(),asc_v.end(),3,dsc_cmp))
        std::cout << "found!\n"; else std::cout << "not found.\n";

    std::cout << "binary_search looking for a 6 in ^v with Vcmp... ";
    if(std::binary_search(asc_v.begin(),asc_v.end(),6,dsc_cmp))
        std::cout << "found!\n"; else std::cout << "not found.\n";


    std::cout << "binary_search looking for a 3 in Vv with Vcmp... ";
    if(std::binary_search(dsc_v.begin(),dsc_v.end(),3,dsc_cmp))
        std::cout << "found!\n"; else std::cout << "not found.\n";

    std::cout << "binary_search looking for a 6 in Vv with Vcmp... ";
    if(std::binary_search(dsc_v.begin(),dsc_v.end(),6,dsc_cmp))
        std::cout << "found!\n"; else std::cout << "not found.\n";

    std::cout << "binary_search looking for a 3 in Vv with ^cmp... ";
    if(std::binary_search(dsc_v.begin(),dsc_v.end(),3,asc_cmp))
        std::cout << "found!\n"; else std::cout << "not found.\n";

    std::cout << "binary_search looking for a 6 in Vv with ^cmp... ";
    if(std::binary_search(dsc_v.begin(),dsc_v.end(),6,asc_cmp))
        std::cout << "found!\n"; else std::cout << "not found.\n";

    std::cout << std::endl;
}

////////////////////////////////////////////////////////////////////////////////
void test_lower_bound()
{
    int myints[] ={1,2,3,4,5,4,3,2,1};
    std::vector<int> asc_v(myints,myints+9);  // 1 2 3 4 5 4 3 2 1
    std::vector<int> dsc_v=asc_v;

    std::sort(asc_v.begin(),asc_v.end()/*, asc_cmp*/);
    std::sort(dsc_v.begin(),dsc_v.end(),dsc_cmp);

    std::cout << "asc_v: ";
    for(auto& it : asc_v)
    {
        static int i = 0;
        printf( "[%d]%d ", i++, it );
    }
    std::cout << std::endl;

    std::cout << "dsc_v: ";
    for(auto& it : dsc_v)
    {
        static int i = 0;
        printf( "[%d]%d ", i++, it );
    }
    std::cout << std::endl;

    auto it = asc_v.begin();

    std::cout << "lower_bound looking for a 3 in ^v with ^cmp... ";
    it = std::lower_bound( asc_v.begin(),asc_v.end(), 3 );
    std::cout << "found at" << it - asc_v.begin() << std::endl;

    std::cout << "lower_bound looking for a 6 in ^v with ^cmp... ";
    it = std::lower_bound(asc_v.begin(),asc_v.end(),6,asc_cmp);
    std::cout << "found at" << it - asc_v.begin() << std::endl;

    std::cout << "lower_bound looking for a 3 in ^v with Vcmp... ";
    it = std::lower_bound(asc_v.begin(),asc_v.end(),3,dsc_cmp);
    std::cout << "found at" << it - asc_v.begin() << std::endl;

    std::cout << "lower_bound looking for a 6 in ^v with Vcmp... ";
    it = std::lower_bound( asc_v.begin(),asc_v.end(),6,dsc_cmp );
    std::cout << "found at" << it - asc_v.begin() << std::endl;


    std::cout << "lower_bound looking for a 3 in Vv with Vcmp... ";
    it = std::lower_bound(dsc_v.begin(),dsc_v.end(),3,dsc_cmp);
    std::cout << "found at" << it - dsc_v.begin() << std::endl;

    std::cout << "lower_bound looking for a 6 in Vv with Vcmp... ";
    it = std::lower_bound(dsc_v.begin(),dsc_v.end(),6,dsc_cmp);
    std::cout << "found at" << it - dsc_v.begin() << std::endl;

    std::cout << "lower_bound looking for a 3 in Vv with ^cmp... ";
    it = std::lower_bound(dsc_v.begin(),dsc_v.end(),3,asc_cmp);
    std::cout << "found at" << it - dsc_v.begin() << std::endl;

    std::cout << "lower_bound looking for a 6 in Vv with ^cmp... ";
    it = std::lower_bound(dsc_v.begin(),dsc_v.end(),6,asc_cmp);
    std::cout << "found at" << it - dsc_v.begin() << std::endl;

    std::cout << std::endl;
}

////////////////////////////////////////////////////////////////////////////////
void test_upper_bound()
{
    int myints[] ={1,2,3,4,5,4,3,2,1};
    std::vector<int> asc_v(myints,myints+9);  // 1 2 3 4 5 4 3 2 1
    std::vector<int> dsc_v=asc_v;

    std::sort(asc_v.begin(),asc_v.end()/*, asc_cmp*/);
    std::sort(dsc_v.begin(),dsc_v.end(),dsc_cmp);

    std::cout << "asc_v: ";
    for(auto& it : asc_v)
    {
        static int i = 0;
        printf( "[%d]%d ", i++, it );
    }
    std::cout << std::endl;

    std::cout << "dsc_v: ";
    for(auto& it : dsc_v)
    {
        static int i = 0;
        printf( "[%d]%d ", i++, it );
    }
    std::cout << std::endl;

    auto it = asc_v.begin();

    std::cout << "upper_bound looking for a 3 in ^v with ^cmp... ";
    it = std::upper_bound(asc_v.begin(),asc_v.end(),3);
    std::cout << "found at" << it - asc_v.begin() << std::endl;

    std::cout << "upper_bound looking for a 6 in ^v with ^cmp... ";
    it = std::upper_bound(asc_v.begin(),asc_v.end(),6,asc_cmp);
    std::cout << "found at" << it - asc_v.begin() << std::endl;

    std::cout << "upper_bound looking for a 3 in ^v with Vcmp... ";
    it = std::upper_bound(asc_v.begin(),asc_v.end(),3,dsc_cmp);
    std::cout << "found at" << it - asc_v.begin() << std::endl;

    std::cout << "upper_bound looking for a 6 in ^v with Vcmp... ";
    it = std::upper_bound(asc_v.begin(),asc_v.end(),6,dsc_cmp);
    std::cout << "found at" << it - asc_v.begin() << std::endl;


    std::cout << "upper_bound looking for a 3 in Vv with Vcmp... ";
    it = std::upper_bound(dsc_v.begin(),dsc_v.end(),3,dsc_cmp);
    std::cout << "found at" << it - dsc_v.begin() << std::endl;

    std::cout << "upper_bound looking for a 6 in Vv with Vcmp... ";
    it = std::upper_bound(dsc_v.begin(),dsc_v.end(),6,dsc_cmp);
    std::cout << "found at" << it - dsc_v.begin() << std::endl;

    std::cout << "upper_bound looking for a 3 in Vv with ^cmp... ";
    it = std::upper_bound(dsc_v.begin(),dsc_v.end(),3,asc_cmp);
    std::cout << "found at" << it - dsc_v.begin() << std::endl;

    std::cout << "upper_bound looking for a 6 in Vv with ^cmp... ";
    it = std::upper_bound(dsc_v.begin(),dsc_v.end(),6,asc_cmp);
    std::cout << "found at" << it - dsc_v.begin() << std::endl;

    std::cout << std::endl;
}


////////////////////////////////////////////////////////////////////////////////
void test_equal_range()
{
    int myints[] ={1,2,3,4,5,4,3,2,1};
    std::vector<int> asc_v(myints,myints+9);  // 1 2 3 4 5 4 3 2 1
    std::vector<int> dsc_v=asc_v;

    std::sort(asc_v.begin(),asc_v.end()/*, asc_cmp*/);
    std::sort(dsc_v.begin(),dsc_v.end(),dsc_cmp);

    std::cout << "asc_v: ";
    for(auto& it : asc_v)
    {
        static int i = 0;
        printf( "[%d]%d ", i++, it );
    }
    std::cout << std::endl;

    std::cout << "dsc_v: ";
    for(auto& it : dsc_v)
    {
        static int i = 0;
        printf( "[%d]%d ", i++, it );
    }
    std::cout << std::endl;

    std::pair<std::vector<int>::iterator,std::vector<int>::iterator> rg;
    std::ptrdiff_t it1;
    std::ptrdiff_t it2;

    std::cout << "equal_range looking for a 3 in ^v with ^cmp... ";
    rg = std::equal_range(asc_v.begin(),asc_v.end(),3);
    it1 = std::distance( asc_v.begin(), rg.first );
    it2 = std::distance( asc_v.begin(), rg.second );
    std::cout << "found at" << it1 << ',' << it2 << std::endl;

    std::cout << "equal_range looking for a 6 in ^v with ^cmp... ";
    rg = std::equal_range(asc_v.begin(),asc_v.end(),6,asc_cmp);
    it1 = std::distance( asc_v.begin(), rg.first );
    it2 = std::distance( asc_v.begin(), rg.second );
    std::cout << "found at" << it1 << ',' << it2 << std::endl;


    //std::cout << "equal_range looking for a 3 in ^v with Vcmp... ";
    //rg = std::equal_range(asc_v.begin(),asc_v.end(),3,dsc_cmp);
    //it1 = std::distance( asc_v.begin(), rg.first );
    //it2 = std::distance( asc_v.begin(), rg.second );
    //std::cout << "found at" << it1 << ',' << it2 << std::endl;


    //std::cout << "equal_range looking for a 6 in ^v with Vcmp... ";
    //rg = std::equal_range(asc_v.begin(),asc_v.end(),6,dsc_cmp);
    //it1 = std::distance( asc_v.begin(), rg.first );
    //it2 = std::distance( asc_v.begin(), rg.second );
    //std::cout << "found at" << it1 << ',' << it2 << std::endl;

    std::cout << "equal_range looking for a 3 in Vv with Vcmp... ";
    rg = std::equal_range(dsc_v.begin(),dsc_v.end(),3,dsc_cmp);
    it1 = std::distance( dsc_v.begin(), rg.first );
    it2 = std::distance( dsc_v.begin(), rg.second );
    std::cout << "found at" << it1 << ',' << it2 << std::endl;

    std::cout << "equal_range looking for a 6 in Vv with Vcmp... ";
    rg = std::equal_range(dsc_v.begin(),dsc_v.end(),6,dsc_cmp);
    it1 = std::distance( dsc_v.begin(), rg.first );
    it2 = std::distance( dsc_v.begin(), rg.second );
    std::cout << "found at" << it1 << ',' << it2 << std::endl;

    //std::cout << "equal_range looking for a 3 in Vv with ^cmp... ";
    //rg = std::equal_range(dsc_v.begin(),dsc_v.end(),3,asc_cmp);
    //it1 = std::distance( dsc_v.begin(), rg.first );
    //it2 = std::distance( dsc_v.begin(), rg.second );
    //std::cout << "found at" << it1 << ',' << it2 << std::endl;

    //std::cout << "equal_range looking for a 6 in Vv with ^cmp... ";
    //rg = std::equal_range(dsc_v.begin(),dsc_v.end(),6,asc_cmp);
    //it1 = std::distance( dsc_v.begin(), rg.first );
    //it2 = std::distance( dsc_v.begin(), rg.second );
    //std::cout << "found at" << it1 << ',' << it2 << std::endl;

    std::cout << std::endl;
}

////////////////////////////////////////////////////////////////////////////////
void main()
{
    test_binary_seach() ;
    test_lower_bound()  ;
    test_upper_bound()  ;
    test_equal_range()  ;

    _getch();
}

////////////////////////////////// END /////////////////////////////////////////

© 著作权归作者所有

雅各宾
粉丝 9
博文 125
码字总数 53022
作品 0
深圳
技术主管
私信 提问
算法与数据结构(七):二分查找法总结

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/Dbyfreedom/article/details/94332149 二分查找法作为一种常见的查找...

dby_freedom
07/14
0
0
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
1K
0
QT容器中的通用算法

今天开始的部分是关于Qt提供的一些通用算法。这部分内容来自C++ GUI Programming with Qt 4, 2nd Edition。 提供了一系列通用的模板函数,用于实现容器上面的基本算法。这部分算法很多依赖于...

晨曦之光
2012/04/13
400
0
python实现lower_bound和upper_bound

由于对于二分法一直都不是很熟悉,这里就用C++中的lowerbound和upperbound练练手。这里用python实现 lowerbound和upperbound本质上用的就是二分法,lowerbound查找有序数组的第一个小于等于目...

mambakb
2018/11/29
0
0
STL lower_bound和upper_bound算法

ForwardIter lowerbound(ForwardIter first, ForwardIter last,const Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。 ForwardIter upperbound(ForwardIter f......

吃一堑消化不良
2016/09/06
58
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
37分钟前
4
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
8
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
11
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
10
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部