深入理解lower_bound与upper_bound

lower_ bound 和 upper_bound是STL中对有序向量的查找算法.

函数原型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//std::lower_bound

//default (1)	
template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
//custom (2)	
template <class ForwardIterator, class T, class Compare>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
  
  
//std::upper_bound

//default (1)	
template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);
//custom (2)	
template <class ForwardIterator, class T, class Compare>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

1.lower_bound

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

也就是函数返回一个向前迭代器,迭代器指向范围[first,last)中的第一个元素,这个元素的比较值不小于val.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//自己的实现
template <typename T> Rank lower_bound(T* arr, Rank lo, Rank hi, const T& val) {
	Rank pos = -1;
	while(lo < hi) {
		Rank mid = (lo + hi) >> 1;
		if (arr[mid] < val) {
			lo = mid + 1;
			pos = lo;
		} else {
			hi = mid;
			pos = hi;
		}
	}
	return pos;
}

//STL

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;
}

2.upper_bound

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

同样是返回一个向前迭代器,迭代器指向范围[first,last)中的第一个元素,该元素需要满足大于val.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//自己的实现
template <typename T> Rank upper_bound(T* arr, Rank lo, Rank hi, const T& val) {
	Rank pos = -1;
	while(lo < hi) {
		Rank mid = (lo + hi) >> 1;
		if (arr[mid] > val) {
			hi = mid;
			pos = hi;
		} else {
			lo = mid + 1;
			pos = lo;
		}
	}
	return pos;
}

//STL

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;
}

总结:

STL的实现方法本质上也是二分,只不过是通过前进迭代器first的移动最终形成了一个[first,last)的区间,然后总是返回该区间内指向第一个元素的迭代器.具体这么实现有什么优势,我暂时还不知道,但既然这么写肯定有用到的地方.

而我自己的版本就是合理控制二分查找的区间划分条件,lower_bound中也就是lo和hi不断逼近最后的极限值为第一个值等于val所在位置(如果存在),最后区间长度为0,返回的也就是lo和hi的位置,否则返回的意义便是第一个大于val的位置(可能会越界).越界的情况也就是所有的元素都小于val.

upper_bound与它类似,不同的地方在于如果存在一个值等于val,此时lo和hi位于最后一个值等于val的元素的位置,那么返回当前位置的下一个位置.

那么如果要形象的解释一下两个函数分别的用法,也就是lower_bound返回查找元素的下界,同理,upper_bound返回的就是查找元素的上界.

在给出一个lower_bound的应用:最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int LIS (vector<int>& vec) {
	vector<int> maxV;
	vector<int>::iterator it;
	maxV.push_back(*vec.begin());
	if (vec.empty()) {
		return 0;
	} else {
		for (it = vec.begin(); it != vec.end(); it++) {
			if (*it > *maxV.rbegin()) {
				maxV.push_back(*it);
			} else {
				*lower_bound(maxV.begin(), maxV.end(), *it) = *it;
			}
		}
	}
	return maxV.size();
}
script>