二分查找法(binary_search,lower_bound,upper_bound,equal

binary_search(二分查找）

//版本一:调用operator<进行比较

template <class ForwardIterator,class StrictWeaklyCompareable>

bool binary_search(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value)

{

    ForwardIterator i = lower_bound(first, last, value);

    return i != last && !(value < *i);

}

//版本二：调用自己定义的function object

template <class ForwardIterator,class T,class StrictWeaklyCompareable>

bool binary_search(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);

　　若找到值==value的，返回true，否则返回false（if and only if [first,last)中存在一个iterator i，使得*i<value&&vale<*i（cmp(*i,value)和cmp(value,*i)）都不成立返回true）

　　对于RandomAccessIterator和其他的Iterator复杂度不同，advance对于RandomAccessIterator为常量，对于ForwardIterator为线性

lower_bound

　　如果[first,last]中有于value相等的元素，便返回指向第一个元素的迭代器，否则返回指向第一个不小于value的元素。如果大于区间内的所有元素则返回last

//版本一:调用operator<进行比较

template <class ForwardIterator,class StrictWeaklyCompareable>

bool lower_bound(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value)

{

    return __lower_bound(first, last, value,distance_type(first), iterator_category(first));

}

// forward iterator 版本

template <class ForwardIterator, class T, class Distance>

ForwardIterator __lower_bound(ForwardIterator first,ForwardIterator last,const T &value,Distance*,forward_iterator_tag)

{

    Distance len = ;

    distance(first, last, len);

    Distance half;

    ForwardIterator middle;

    while(len > ) {

        half = len >> ;

        advance(middle, half);

        if(*middle < value) {

            first = middle;

            ++first;

            len = len - half - ;

        } else

            len = half;

    }

    return first;

}

//random access iterator 版本

template <class RandomAccessIterator, class T, class Distance>

RandomAccessIterator __lower_bound(RandomAccessIterator first,RandomAccessIterator last,const T &value,Distance*,random_access_iterator_tag)

{

    Distance len = last - first;

    Distance half;

    RandomAccessIterator middle;

    while(len > )

    {

        half = len >> ;

        middle = first + half;

        if(*middle < value)

        {

            first = middle + ;

            len = len - half - ;

        } else

            len = half;

    }

    return first;

}

//版本二：调用自己定义的function object

template <class ForwardIterator,class T,class StrictWeaklyCompareable>

bool lower_bound(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);

　　为二分查找的一种

若存在，返回的iterator指向第一个值为value的元素
若不存在，返回第一个不小于value的元素（也即是不破坏元素顺序下第一个可安插value的位置）
若比range中的所有元素都大，则指向end

upper_bound

　　返回在不破坏元素顺序的情况下可插入value的最后一个位置。

//版本一：operator<

template <class BidirectionalIterator>

bool prev_premutation(BidirectionalIterator first,BidirectionalIterator last);

//版本二：用自定义的function object

template <class BidirectionalIterator,class StrictweakOrdering>

bool prev_premutation(BidirectionalIterator first,BidirectionalIterator last,StrictweakOrdering cmo);

//版本一:调用operator<进行比较

template <class ForwardIterator,class StrictWeaklyCompareable>

bool upper_bound(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value)

{

    return __upper_bound(first, last, value,distance_type(first), iterator_category(first));

}

// forward iterator 版本

template <class ForwardIterator, class T, class Distance>

ForwardIterator __upper_bound(ForwardIterator first,ForwardIterator last,const T &value,Distance*,forward_iterator_tag)

{

    Distance len = ;

    distance(first, last, len);

    Distance half;

    ForwardIterator middle;

    while(len > )

    {

        half = len >> ;

        advance(middle, half);

        if(value < *middle)

            len = half;

        else {

            first = middle;

            ++first;

            len = len - half - ;

        }

    }

    return first;

}

// random access iterator 版本

template <class RandomAccessIterator, class T, class Distance>

RandomAccessIterator __upper_bound(RandomAccessIterator first,RandomAccessIterator last,const T &value,Distance*,random_access_iterator_tag)

{

    Distance len = last - first;

    Distance half;

    RandomAccessIterator middle;

    while(len > ) {

        half = len >> ;

        middle = first + half;

        if(value < *middle)

            len = half;

        else {

            first = middle + ;

            len = len - half - ;

        }

    }

    return first;

}

//版本二：调用自己定义的function object

template <class ForwardIterator,class T,class StrictWeaklyCompareable>

bool upper_bound(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);

　　为二分查找的一种

若存在，返回最后一个元素的下一位置
若不再在，返回最后一个可安插value的位置
若比range中的所有元素都大，则指向end

equal_range

　　返回值是一对i，j，以pair的形式返回，i是第一个可安插value的位置，j是不破坏原来顺序下最后一个可安插的位置，[i,j)中的每个元素都与value相等，所以equal_range的返回值是[first,last)的一个子区间，若range内没有任何一个元素与value等价，返回的是个空range；不破坏原来的range下只有一个位置可安插value，pair的两个元素都指向该位置。

//版本一:由iterator i，j构成的pair，i为[fisrt,last)中最远的iterator，使得[fisrt,i)中每个iterator k都满足*k<=value

//j是[fisrt,last)最远的iterator，使得[fisrt,j)中每个iterator k都满足value<*k不为真，对于[i,j)中每个iterator k，满足value

//<*k和*k<value都不为真

template <class ForwardIterator,class StrictWeaklyCompareable>

pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value)

{

    return __equal_range(first, last, value, distance_type(first),iterator_category(first));

}

// ForwardIterator 版本

template <class ForwardIterator, class T, class Distance>

pair<ForwardIterator, ForwardIterator>

__equal_range(ForwardIterator first, ForwardIterator last, const T& value,

              Distance*, forward_iterator_tag) {

  Distance len = ;

  distance(first, last, len);

  Distance half;

  ForwardIterator middle, left, right;

  while (len > ) { // 奇怪？ 为什么不直接用 lower_bound 、 upper_bound ， 而是等找到值再用？

                    // --> 我觉得是效率方面的考虑。先找 value ，这时左右两个区间可能已经缩小了许多，

                    // 再利用 lower_bound 和 upper_bound 代价小很多

    half = len >> ;

    middle = first;

    advance(middle, half);

    if (*middle < value) {

      first = middle;

      ++first;

      len = len - half - ;

    }

    else if (value < *middle)

      len = half;

    else {

      left = lower_bound(first, middle, value);

      advance(first, len);

      right = upper_bound(++middle, first, value);

      return pair<ForwardIterator, ForwardIterator>(left, right);

    }

  }

  return pair<ForwardIterator, ForwardIterator>(first, first);

}

// RandomAccessIterator 版本

template <class RandomAccessIterator, class T, class Distance>

pair<RandomAccessIterator, RandomAccessIterator>

__equal_range(RandomAccessIterator first, RandomAccessIterator last,

              const T& value, Distance*, random_access_iterator_tag) {

  Distance len = last - first;

  Distance half;

  RandomAccessIterator middle, left, right;

  while (len > ) {

    half = len >> ;

    middle = first + half;

    if (*middle < value) {

      first = middle + ;

      len = len - half - ;

    }

    else if (value < *middle)

      len = half;

    else {

      left = lower_bound(first, middle, value);

      right = upper_bound(++middle, first + len, value);

      return pair<RandomAccessIterator, RandomAccessIterator>(left,

                                                              right);

    }

  }

  return pair<RandomAccessIterator, RandomAccessIterator>(first, first);

}

//版本二：调用自己定义的function object

template <class ForwardIterator,class T,class StrictWeaklyCompareable>

pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);

巴特西

二分查找法(binary_search,lower_bound,upper_bound,equal_range)

binary_search(二分查找）

lower_bound

upper_bound

equal_range

最新文章

热门文章