首页 > 代码库 > 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算法之二分法查找