C++ algorithm Binary search

C++ algorithm

字数统计: 1.9k阅读时长: 9 min

 2021/05/21   Share

C++ algorithm Binary search

这一部分是有关于查找的。使用的前提是查找范围内的元素有序。

这些函数的参数列表都相同，但是返回值有些许的不同。

函数名	函数功能
lower_bound	查找范围内第一个大于等于 val 的元素
upper_bound	查找范围内第一个大于 val 的元素
equal_range	返回包含范围 [first,last) 中元素等价于 val 的边界。即 [lower_bound, upper_bound)
binary_search	查找范围内有没有等于 val 的元素，有则返回 true，无则返回 false。

lower_bound

返回一个迭代器，该迭代器指向范围 [first,last) 中的第一个元素，且其比较值不小于 val。

源代码：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 last 迭代器，第三参数为 val ，第四个参数为 Compare 方法。
template <class _FwdIt, class _Ty, class _Pr>
_NODISCARD _FwdIt lower_bound(_FwdIt _First, const _FwdIt _Last, const _Ty& _Val, _Pr _Pred) {
    // find first element not before _Val, using _Pred
    _Adl_verify_range(_First, _Last);
    auto _UFirst                = _Get_unwrapped(_First);
    _Iter_diff_t<_FwdIt> _Count = _STD distance(_UFirst, _Get_unwrapped(_Last));

    while (0 < _Count) { // divide and conquer, find half that contains answer
        const _Iter_diff_t<_FwdIt> _Count2 = _Count >> 1; // TRANSITION, VSO#433486
        const auto _UMid                   = _STD next(_UFirst, _Count2);
        if (_Pred(*_UMid, _Val)) { // try top half
            _UFirst = _Next_iter(_UMid);
            _Count -= _Count2 + 1;
        } else {
            _Count = _Count2;
        }
    }

    _Seek_wrapped(_First, _UFirst);
    return _First;
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第四参数的比较方式。
template <class _FwdIt, class _Ty>
_NODISCARD _FwdIt lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) {
    // find first element not before _Val, using operator<
    return _STD lower_bound(_First, _Last, _Val, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

upper_bound

返回一个迭代器，该迭代器指向范围 [first,last) 中第一个比 val 大的元素。

源代码：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 last 迭代器，第三参数为 val ，第四个参数为 Compare 方法。
template <class _FwdIt, class _Ty, class _Pr>
_NODISCARD _FwdIt upper_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Pr _Pred) {
    // find first element that _Val is before, using _Pred
    _Adl_verify_range(_First, _Last);
    auto _UFirst                = _Get_unwrapped(_First);
    _Iter_diff_t<_FwdIt> _Count = _STD distance(_UFirst, _Get_unwrapped(_Last));

    while (0 < _Count) { // divide and conquer, find half that contains answer
        _Iter_diff_t<_FwdIt> _Count2 = _Count >> 1; // TRANSITION, VSO#433486
        const auto _UMid             = _STD next(_UFirst, _Count2);
        if (_Pred(_Val, *_UMid)) {
            _Count = _Count2;
        } else { // try top half
            _UFirst = _Next_iter(_UMid);
            _Count -= _Count2 + 1;
        }
    }

    _Seek_wrapped(_First, _UFirst);
    return _First;
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第四参数的比较方式。
template <class _FwdIt, class _Ty>
_NODISCARD _FwdIt upper_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) {
    // find first element that _Val is before, using operator<
    return _STD upper_bound(_First, _Last, _Val, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

equal_range

返回包含范围 [first,last) 中所有元素的子范围的边界，其值等价于 val。

返回一个 pair 对象，其 pair::first 是子范围的下界， pair::second 是子范围的上界。

这些值分别与 lower_bound 和 upper_bound 函数返回的值相同。

如果 val 不等于范围内的任何值，则返回的子范围长度为 0，如果有，则两个迭代器都指向比 val 更大的最近值，如果val比范围内的所有元素都大，则指向 last。

源代码：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 last 迭代器，第三参数为 val ，第四个参数为 Compare 方法。
template <class _FwdIt, class _Ty, class _Pr>
_NODISCARD pair<_FwdIt, _FwdIt> equal_range(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Pr _Pred) {
    // find range equivalent to _Val, using _Pred
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);

    using _Diff  = _Iter_diff_t<_FwdIt>;
    _Diff _Count = _STD distance(_UFirst, _ULast);

    for (;;) { // divide and conquer, check midpoint
        if (_Count <= 0) {
            _Seek_wrapped(_Last, _UFirst); // empty range
            _Seek_wrapped(_First, _UFirst);
            break;
        }

        _Diff _Count2    = _Count >> 1; // TRANSITION, VSO#433486
        const auto _UMid = _STD next(_UFirst, _Count2);
        if (_DEBUG_LT_PRED(_Pred, *_UMid, _Val)) { // range begins above _UMid, loop
            _UFirst = _Next_iter(_UMid);
            _Count -= _Count2 + 1;
        } else if (_Pred(_Val, *_UMid)) {
            _Count = _Count2; // range in first half, loop
        } else { // range straddles _UMid, find each end and return
            auto _UFirst2 = _STD lower_bound(_UFirst, _UMid, _Val, _Pass_fn(_Pred));
            _STD advance(_UFirst, _Count);
            auto _ULast2 = _STD upper_bound(_Next_iter(_UMid), _UFirst, _Val, _Pass_fn(_Pred));
            _Seek_wrapped(_Last, _ULast2);
            _Seek_wrapped(_First, _UFirst2);
            break;
        }
    }

    return {_First, _Last};
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第四参数的比较方式。
template <class _FwdIt, class _Ty>
_NODISCARD pair<_FwdIt, _FwdIt> equal_range(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) {
    // find range equivalent to _Val, using operator<
    return _STD equal_range(_First, _Last, _Val, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

binary_search

如果 [first,last) 范围内的有元素等价于 val，则返回 true，否则返回 false。

源代码：

//第一个版本，如果写了 Compare 方法，即需要使用这个方式。
//第一参数为 first 迭代器，第二参数为 last 迭代器，第三参数为 val ，第四个参数为 Compare 方法。
template <class _FwdIt, class _Ty, class _Pr>
_NODISCARD bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Pr _Pred) {
    // test if _Val equivalent to some element, using _Pred
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    _UFirst           = _STD lower_bound(_UFirst, _ULast, _Val, _Pass_fn(_Pred));
    return _UFirst != _ULast && !_Pred(_Val, *_UFirst);
}
//第二个版本，该版本事实上就是使用了第一个版本，如果重载操作符 < ，即可改变第四参数的比较方式。
template <class _FwdIt, class _Ty>
_NODISCARD bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) {
    // test if _Val equivalent to some element, using operator<
    return _STD binary_search(_First, _Last, _Val, less<>());
}

使用 cmp 则使用第一个版本，使用重载 < 则使用第二个版本。

示例：

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	vector<int> a{ 1,2,3,4,5,5,10,15,30 };
	//注意 lower_bound 与 upper_bound 返回的是迭代器
	cout << "查找第一个大于等于5的值：" << *lower_bound(a.begin(), a.end(), 5) << endl;
	cout << "查找第一个大于5的值：    " << *upper_bound(a.begin(), a.end(), 5) << endl;
	cout << endl;
	//equal_range 的三种情形
	//注意 equal_range 返回的是 pair
	//结构为 pair<std::vector<int>::iterator,std::vector<int>::iterator>
	//就是一个 pair 里面装了两个指针，第一个为头，第二个为尾
	auto bound1 = equal_range(a.begin(), a.end(), 5);
	cout << "值为 5 的元素有几个：" << bound1.second - bound1.first << endl;
	auto bound2 = equal_range(a.begin(), a.end(), 6);
	cout << "值为 6 的元素有几个：" << bound2.second - bound2.first << endl;
	auto bound3 = equal_range(a.begin(), a.end(), 100);
	cout << "值为 6 的元素有几个：" << bound3.second - bound3.first << endl;
	cout << endl;
	//查找 val 是否存在
	cout << "是否存在等于 5 的值：" << binary_search(a.begin(), a.end(), 5) << endl;
	cout << "是否存在等于 5 的值：" << binary_search(a.begin(), a.end(), 6) << endl;

	return 0;
}

输出：

查找第一个大于等于5的值：5
查找第一个大于5的值：    10

值为 5 的元素有几个：2
值为 6 的元素有几个：0
值为 6 的元素有几个：0

是否存在等于 5 的值：1
是否存在等于 5 的值：0

Binary search 总结

和 sorting 一样，每个函数都可以自定义排序规则。

都具有两个版本，一个有 Compare，一个没有。而且 Compare 参数放在参数列表的最后。

原文作者：F_JustWei

原文链接：http://139.196.79.90/2021/05/21/C-algorithm-Binary-search/

发表日期：May 21st 2021, 9:58:33 pm

更新日期：May 21st 2021, 11:50:28 pm

Next Post

C++ algorithm Sorting
Previous Post

C++ tuple

CATALOG

1. C++ algorithm Binary search
1. 1.0.1. lower_bound
  1. 1.0.1.0.1. 源代码：
1.0.2. upper_bound
1. 1.0.2.0.1. 源代码：

1.0.3. equal_range

1.0.3.0.1. 源代码：

1.0.4. binary_search

1.0.4.0.1. 源代码：

2. 示例：

3. 输出：

4. Binary search 总结

