[C++] upper_bound和lower

upper_bound 源码

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;

}

lower_bound 源码

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;

}

若val在原数组中存在,则upper_bound返回最后一个val的位置,lower_bound返回第一个val的位置

若val在原数组中不存在,则upper_bound和lower_bound返回的都是val因放在哪个位置而不影响原序列

巴特西

[C++] upper_bound和lower_bound

upper_bound 源码

lower_bound 源码

最新文章

热门文章