当前位置: 代码迷 >> 综合 >> STL 二分查找(binary_search(),lower_bound(),upper_bound() )
  详细解决方案

STL 二分查找(binary_search(),lower_bound(),upper_bound() )

热度:104   发布时间:2023-11-08 17:44:45.0

1.二分查找功能(binary_search())

函数功能: 在数组中以二分法检索的方式查找,若在数组(要求数组元素非递减)中查找到indx元素则返回其下标,若查找不到则返回值为假。

函数模板:binary_search(arr[], size , indx)
参数说明: arr[]: 数组首地址;
size: 数组元素个数;
indx: 需要查找的值。

2. lower_bound():

函数功能: 函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置如果所有元素都小于val,则返回last的位置

举例如下:

一个数组number序列为:4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标

pos = lower_bound( number, number + 8, 3) - number,pos = 0. //即number数组的下标为0的位置。
pos = lower_bound( number, number + 8, 9) - number, pos = 1 //即number数组的下标为1的位置(即10所在的位置)。
pos = lower_bound( number, number + 8, 111) - number, pos = 8 //即number数组的下标为8的位置(但下标上限为7,所以返回最后一个元素的下一个元素)。

返回查找元素的第一个可安插位置,也就是“元素值>=查找值”的第一个元素的位置

3.upper_bound():

函数功能:函数upper_bound()返回的在前闭后开区间查找的关键字的上界,返回大于val的第一个元素位置

例如:一个数组number序列1,2,2,4.upper_bound(2)后,返回的位置是3(下标)也就是4所在的位置,同样,如果插入元素大于数组中全部元素,返回的是last。(注意:数组下标越界)
返回查找元素的最后一个可安插位置,也就是“元素值>查找值”的第一个元素的位置

注意:
lower_bound(val): 返回容器中第一个值【大于或等于】val的元素的iterator位置。
upper_bound(val): 返回容器中第一个值【大于】val的元素的iterator位置。

4.拓展:

insert()用法:
比如vec中已经有了{0,1,3,5},这时要放入4

ite=lower_bound(vec.begin(),vec.end(),4);   //找到待插入的位置
vec.insert(ite,4);          //将元素插入

则std::lower_bound( _rows.begin(), _rows.end(), 4);将会返回5,就是应该插入的那个位置后面的那个值。然后_rows.insert( iter, 4);这句将按照从小到大的顺序将4放进去,最后的顺序是{0,1,3,4,5}