华师一附中OI组

标题: upper_bound 和lower_bound的使用 [打印本页]

作者: admin 时间: 2018-7-13 16:18
标题: upper_bound 和lower_bound的使用
upper_bound 和lower_bound是二分查找，所以效率略高，并可以精简程序，但是使用要小心。可续可能要先搭配equal_range()，binary_search()使用。

upper_bound（i）返回的是键值为i的元素可以插入的最后一个位置（上界）
lowe_bound（i）返回的是键值为i的元素可以插入的位置的第一个位置（下界）。

怎么理解呢，举例：
在升序的set里面
set里没有元素i的时候，两个元素的返回值是一样的。
1 2 4 5 这个序列，upp（3）和low（3）都返回位置2（下标）

如果只有一个元素i，low返回那个元素的位置，而upp返回那个元素的位置的后一个位置。
1 2 4 5 这个序列upp（2）返回下标2而low（2）返回下标1

多个元素i，low返回那个元素的位置，upp返回那多个元素中的最后一个的后一个位置。
1 2 2 4 5 这个序列 upp（2）返回下标3的位置，low（2）返回下标1的位置。

！！！！！！！！！！！！！
特别注意：举例在一个升序的容器里，如果所有元素都大于i则，upp和low都返回begin。都小于i则返回end（越界了）。

最后再来一句，看是否好理解一些。

terator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。
iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值<=key的最后一个元素的后一个元素。
★降序排列的容器：
iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值<= key的第一个元素。
iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值>=key的最后一个元素的后一个元素。

欢迎光临华师一附中OI组 (http://hsyit.cn/)