深入理解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>