STL中有序序列的查找算法

用户9831583

发布于 2022-06-16 15:19:24

4460

发布于 2022-06-16 15:19:24

文章被收录于专栏：码出名企路

1.binary_search()

二分查找一般比顺序搜索要快，但要求序列中的元素是有序的。

参数定义：binary_search() 实现了一个二分查找算法。它会在前两个参数指定范围内搜索等同于第三个参数的元素。这个序列中的元素必须被排成升序序列或者至少相对于所查找元素是有序的。

返回值：如果找到第三个参数，这个算法会返回布尔值 true，否则返回 false。

注意：binary_search() 能告诉我们元素是否在这个序列中，但当它在序列中时，却不能告诉我们它的位置。

 std::list<int> values {17, 11, 40, 36, 22, 54, 48, 70, 61, 82, 78, 89, 99, 92, 43};
    values.sort ();
    int wanted {22};  
    if(std::binary_search(std::begin(values), std::end(values), wanted))
        std::cout << wanted << " is definitely in there - somewhere..."<< std::endl;
    else
        std::cout << wanted << " cannot be found - maybe you got it wrong..." << std::endl;

结果显示：

特别注意：不能对 list 容器中的元素应用 sort() 算法，因为它需要的是随机访问迭代器，而 list 容器只提供了双向迭代器。因为这个 list 定义了一个成员函数sort()，可以将全部的元素排成升序，所以可以用这个函数来对容器中的元素进行排序。

另一个版本的 binary_search() 接受一个额外的参数，它是一个用于查找元素的函数对象；显然，它必须和用于对被查找序列进行排序的比较操作有相同的效果。

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <iterator>
#include <list>

int main()
{
    std::list<int> values {17, 11, 40, 36, 22, 54, 48, 70, 61, 82, 78, 89, 99, 92, 43};
    values.sort ();
    int wanted {22};  
    if(std::binary_search(std::begin(values), std::end(values), wanted))
        std::cout << wanted << " is definitely in there - somewhere..."<< std::endl;
    else
        std::cout << wanted << " cannot be found - maybe you got it wrong..." << std::endl;
    std::cout << "The lower bound for "<< wanted<< " is "<< *std:: lower_bound (std::begin (values), std::end(values), wanted)<< std::endl;
}

2.lower_bound()

在前两个参数指定的范围内查找不小于第三个参数的第一个元素，也就是说大于等于第三个参数的第一个元素。前两个参数必须是正向迭代器。

    std::cout << "The lower bound for "<< wanted<< " is "<< *std:: lower_bound (std::begin (values), std::end(values), wanted)<< std::endl;

结果显示：

该算法还有额外的版本，它接受一个函数对象作为第三个参数，用于指定序列排序所使用的比较。

3.upper_bound()

在前两个参数定义的范围内查找大于第三个参数的第一个元素。对于这两个算法，它们所查找的序列都必须是有序的，而且它们被假定是使用 < 运算符来排序的。

std::cout<<"The upper bound for " << wanted<< " is " << *std::upper_bound (std::begin (values), std:: end (values), wanted)<< std::endl;

结果显示：

该算法还有额外的版本，它接受一个函数对象作为第三个参数，用于指定序列排序所使用的比较。

4.equal_range()

找出有序序列中所有和给定元素相等的元素。

参数定义：前两个参数是指定序列的两个正向迭代器，第三个参数是要查找的元素。

返回值：返回一个 pair 对象，它有两个正向迭代器成员， first 指向的是不小于第三个参数的一个元素，second 指向大于第三个参数的一个元素。

可以用下面这些语句来替换前一个代码段中的两条输出语句：

    auto pr = std::equal_range(std::begin(values) , std::end(values), wanted);
    std::cout << "the lower bound for " << wanted << " is " << *pr.first << std::endl;
    std::cout << "Tthe upper bound for " << wanted << " is " << *pr.second << std::endl;

结果显示：

综合应用：

    #include <iostream>                          
    #include <list>                                  
    #include <algorithm>                            
    #include <iterator>                          
    int main()
    {
        std::list<int> values {17, 11, 40, 13, 22, 54, 48, 70, 22, 61, 82, 78, 22, 89, 99, 92, 43};
      
        std::cout << "The elements in the original sequence are:\n";
        std::copy(std::begin(values), std::end(values), std::ostream_iterator<int> {std::cout, " "});
        std::cout << std::endl;

        int wanted {22};
        //第一个分区操作保证严格小于 wanted 的所有元素都在左分区中，这些元素不需要是有序的
        //这个操作也保证所有大于等于 wanted 的元素都在右分区中，所以它们都在 wanted 的后面，而且也不需要是有序的                          
        std::partition(std::begin(values), std::end(values),[wanted](double value) { return value < wanted; });
        //第二个分区操作会被应用到第一个操作的结果上。表达式 !(wanted<value) 等同于 (value <=wanted)
        //因此作为结果，小于等于 wanted 的所有元素会出现在左分区中，而且所有严格大于 wanted 的元素会在右分区中
        //这个操作的效果是将所有 wanted 的实例移到左分区中，所以它们被一起作为左分区的最后一个元素
        std::partition(std::begin(values), std::end(values),[wanted](double value) { return !(wanted < value); });
    
        std::cout << "The elements after partitioning are:\n";
        std::copy(std::begin(values), std::end(values), std::ostream_iterator<int> {std::cout, " "});
        std::cout << std::endl;
        
        //equal_range() 找到的下边界指向 22 的第一个匹配项，上边界指向 22 的最后一个匹配项的后面，即值为 48 的元素
        auto pr = std::equal_range(std::begin(values), std::end(values), wanted);
        std::cout << "The lower bound for " << wanted << " is " << *pr.first << std::endl;
        std::cout << "The upper bound for " << wanted << " is " << *pr.second << std::endl;

        std::cout << "\nThe elements found by equal_range() are:\n";
        std::copy(pr.first, pr.second, std::ostream_iterator<int> {std::cout, " "});
        std::cout << std::endl;
    }

结果显示：