华师一附中OI组

标题: upper_bound()和low_bound函数的基本使用和理解 [打印本页]

作者: admin 时间: 2018-8-11 16:59
标题: upper_bound()和low_bound函数的基本使用和理解
前提：一个非降序列！！！！！！

lower_bound()函数使用:

它的参数就是：

1.一个数组元素的地址（或者数组名来表示这个数组的首地址，用来表示这个数组的开头比较的元素的地址，不一定要是首地址，只是用于比较的“首”地址），

2.一个数组元素的地址（对应的这个数组里边任意一个元素的地址，表示这个二分里边的比较的"结尾'地址），

3.就是一个你要二分查找的那个数。

返回值:

返回值就是返回第一次出现大于等于那个要查找的数的地址，

注意两点，

第一，是地址，不是指那个要查找的数的下标，所以就注定了在这个函数的后边就要减去一个尾巴，那就是这个数组的数组名，即这个数组的首地址,只有这样才代表那个要查找的数字的下标，当然如果没有找到那个数，也是会返回的，那么返回的又会是什么呢？下面第二点。

第二点，那就是要大于等于那个数，等于好理解，大于怎么理解呢，比如说我并没有找到那个数，加入一个的数组里边就有5个数，分别是1,1,1,3,5,而我需要找的那个数就是2，怎么返回呢？小编告诉你哦，就是返回那个第一个大于2的数的地址，就是返回3的地址，那么再有一组数据就是5个数1,1,1,3,3，还是需要找寻2，那么该返回什么呢？那就是第一个3的地址。下边来段代码你理解下吧

：#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int k,n=10;
int a[10]={1,1,1,3,3,5,5,5,5,6};
int main()
{
for(int i=0;i<n;i++)cout<<a[i]<<" ";
cout<<endl;
while(scanf("%d",&k))
{
cout<<k<<"的第一个大于等于它的位置在"<<((lower_bound(a,a+n,k))-a)+1<<endl;
}
}

upper_bound函数的用法lower_bound函数的用法相似，不过这个唯一的不同就是返回的是第一个比我要找的那个数大的数的地址，注意，这里并没有等于，也就是说如果在5个数1,1,2,2,4，里边寻找3，那么就会返回4的地址，下边代码实现：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int k,n=10;
int a[10]={1,1,1,3,3,5,5,5,5,6};
int main()
{
for(int i=0;i<n;i++)cout<<a[i]<<" ";
cout<<endl;
while(scanf("%d",&k))
{
cout<<k<<"的第一个大于它的位置在"<<((upper_bound(a,a+n,k))-a)+1<<endl;
}
}

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