一、前言

本文使用C++来实现有序容器的二分搜索算法。

说明:本文代码需支持C++标准编译器编译,以及可选单元测试工具googletest

项目地址:algorithm

二、函数声明

// iterator_traits<It>::value_tpye 用于获取模版中迭代器It的类型
template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

// 给定有序迭代器区间 [first, end), 返回第一个大于 value 的迭代器
template<class It, 
         class T = value_type_t<It>, 
         class Compare = std::less<value_type_t<It>>>
It UpperBound(It first, It end, const T& value, Compare cmp = Compare())
// 给定有序迭代器区间 [first, end), 返回第一个大于等于 value 的迭代器
// 若不存在则返回 first 迭代器
template<class It, 
                 class T = value_type_t<It>, 
         class Compare = std::less<value_type_t<It>>>
It Lowerbound(It first, It end, const T& value, Compare cmp = Compare())
// 给定有序迭代器区间 [first, end), 返回是否有等于 value 的迭代器
template<class It, 
         class T = value_type_t<It>, 
         class Compare = std::less<value_type_t<It>>>
bool BinarySearch(It first, It end, const T& value, Compare cmp = Compare())

三、函数实现

3.1 UpperBound

// 给定有序迭代器区间 [first, end), 返回第一个大于 value 的迭代器
// T - 迭代器类型
// Compare - 默认比较函数为std::less
template<class It, 
         class T = value_type_t<It>, 
         class Compare = std::less<value_type_t<It>>>
It UpperBound(It first, It end, const T& value, Compare cmp = Compare()) {
    auto count = std::distance(first, end);  /* 计算长度 */
    auto it = first;                    
    while (count > 0) {
        it = first;              /* 从左区间开始 */
        auto step = count / 2;   /* 获取到中点位置步长 */
        std::advance(it, step);  /* it 设置为中点 */
        if (!cmp(value, *it)) {  /* value >= mid */
            first = ++it;        /* 设置左区间 first 为 it + 1 */
            count -= step + 1;   /* 总步长 = 总步长 - (前进步长 + 1) */
        }else {                                     /* value < mid */
            count = step;        /* 总步长 = 前进步长(总步长减半) */
        }
    }
    return first;
}

3.2 LowerBound

// 给定有序迭代器区间 [first, end), 返回第一个大于等于 value 的迭代器
// T - 迭代器类型
// Compare - 默认比较函数为std::less
template<class It, 
         class T = value_type_t<It>, 
         class Compare = std::less<value_type_t<It>>>
It LowerBound(It first, It end, const T& value, Compare cmp = Compare()) {
    auto count = std::distance(first, end);
    auto it = first;
    while (count > 0) {
        it = first;                          /* 从左区间开始 */
        auto step = count / 2;  /* 获取到中点位置步长 */
        std::advance(it, step); /* it 设置为中点 */
        if (cmp(*it, value)) {  /* mid < value */
            first = ++it;       /* 设置左区间 first 为 it + 1 */
            count -= step + 1;  /* 总步长 = 总步长 - (前进步长 + 1) */
        }else {                 /* mid >= value */
            count = step;       /* 总步长 = 前进步长(总步长减半) */
        }
    }
    return first;
}

3.3 BinarySearch

// 给定有序迭代器区间 [first, end), 返回是否有等于 value 的迭代器
// T - 迭代器类型
// Compare - 默认比较函数为std::less
template<class It, 
         class T = value_type_t<It>, 
         class Compare = std::less<value_type_t<It>>>
bool BinarySearch(It first, It end, const T& value, Compare cmp = Compare()) {
    first = LowerBound(first, end, value, cmp);/* 返回第一个大于等于 value 值*/
    return (!(first == end) && !(cmp(value, *first))); /* 判断是否相等/不存在 */
}

四、单元测试

TEST_F(BinarySearchTest, UpperBound) {
    std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
    auto it = UpperBound(data.begin(), data.end(), 4);
    auto step = std::distance(data.begin(), it);
    ASSERT_EQ(step, 10);
    it = UpperBound(data.begin(), data.end(), 0);
    ASSERT_EQ(it, data.begin());
    it = UpperBound(data.begin(), data.end(), 7);
    ASSERT_EQ(it, data.end());
}

TEST_F(BinarySearchTest, Lowerbound) {
    std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
    auto it = LowerBound(data.begin(), data.end(), 4);
    auto step = std::distance(data.begin(), it);
    ASSERT_EQ(step, 7);
    it = LowerBound(data.begin(), data.end(), 0);
    ASSERT_EQ(data.begin(), it);
}

TEST_F(BinarySearchTest, BinarySearch) {
    std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
    ASSERT_EQ(BinarySearch(data.begin(), data.end(), 3), true);
    ASSERT_EQ(BinarySearch(data.begin(), data.end(), 0), false);
    ASSERT_EQ(BinarySearch(data.begin(), data.end(), 7), false);
}
Last modification:May 12th, 2020 at 07:45 pm