首页 > 代码库 > stl_algorithm算法之二分法查找
stl_algorithm算法之二分法查找
二分法查找:
7.60、template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val) { ForwardIterator it; iterator_traits < ForwardIterator>::difference_type count, step; count = distance(first,last); while (count > 0) { it = first; step = count/2; advance (it,step); if (*it<val) { // or: if (comp(*it,val)), for version (2) first=++it; count -= step+1; } else count = step; } return first; }
7.61、template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val) { ForwardIterator it; iterator_traits<ForwardIterator>::difference_type count, step; count = std::distance(first,last); while (count>0) { it = first; step=count/2; std::advance (it,step); if (!(val<*it)) // or: if (!comp(val,*it)), for version (2) { first = ++it; count -= step+1; } else count=step; } return first; }
7.62、template <class ForwardIterator, class T> pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val) { ForwardIterator it = std::lower_bound (first,last,val); return std::make_pair ( it, std::upper_bound(it,last,val) ); }
7.63、template <class ForwardIterator, class T> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val) { first = std::lower_bound(first,last,val); return (first!=last && !(val<*first)); }
stl_algorithm算法之二分法查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。