【STL】二分查找函数 lower_bound 和 upper_bound
一、 lower_bound
【功能】
在数组a中从a[begin]开始到a[end - 1]按照cmp函数来比较进行二分查找第一个大于等于k的数的地址，如果有第一个大于等于k的数则返回该数的地址，否则返回a[end]的地址。
【头文件】
algorithm
【模板】
lower_bound(a + begin, a + end, k, cmp); 首地址（a + begin） 必要 末地址（a + end） 必要 需要比较的值 必要 比较函数表示序列如何有序 （多数情况下适用于对结构体的搜索） 选要
【必要条件】
必须是有序数组
【例子】
# include <cstdio>
# include <iostream>
# include <cmath>
# include <cstring>
# include <algorithm>
using namespace std;
const int NR = 100;
int n = 6;
int a[50] = {0, 1, 5, 7, 9, 23, 60};
int main() {
cout<<"a数组从a[1]到a[n]这n个数中第一个大于等于10的数的地址为"<<lower_bound(a+1,a+n+1,10)<<endl;
cout<<"a数组从a[1]到a[n]这n个数中第一个大于等于9的数的位置为"<<lower_bound(a+1,a+n+1,9)-a<<endl;
cout<<"a数组从a[0]到a[n-1]这n个数中第一大于于等于10的数的位置为"<<lower_bound(a,a+n,10)-a<<endl;
cout<<"a数组从a[1]到a[n]这n个数中第一个大于等于13的数的位置为"<<lower_bound(a+1,a+n+1,13)-a<<endl;
cout<<"a数组从a[1]到a[n]这n个数中第一个大于等于7的数的位置为"<<lower_bound(a+1,a+n+1,7)-a<<endl;
cout<<"a数组从a[1]到a[n]这n个数中第一个大于等于10000的数的位置为"<<lower_bound(a+1,a+n+1,10000)-a<<endl;
return 0;
}
/*
a数组从a[1]到a[n]这n个数中第一个大于等于10的数的地址为0x46a054
a数组从a[1]到a[n]这n个数中第一个大于等于9的数的位置为4
a数组从a[0]到a[n-1]这n个数中第一大于于等于10的数的位置为5
a数组从a[1]到a[n]这n个数中第一个大于等于13的数的位置为5
a数组从a[1]到a[n]这n个数中第一个大于等于7的数的位置为3
a数组从a[1]到a[n]这n个数中第一个大于等于10000的数的位置为7
*/二、upper_bound
【功能】
在数组a中从a[begin]开始到a[end - 1]按照cmp函数来比较进行二分查找第一个大于k的数的地址，如果有第一个大于k的数则返回该数的地址，否则返回a[end]的地址。
【头文件】
algorithm
【必要条件】
从a[begin]开始到a[end - 1]的序列是有序序列。
【模板】
upper_bound(a + begin, a + end, k, cmp); 首地址（a + begin） 必要 末地址（a + end） 必要 需要比较的值 必要 比较函数表示序列如何有序（多数情况下适用于对结构体的搜索） 选要
【例子】
# include <cstdio>
# include <iostream>
# include <cmath>
# include <cstring>
# include <algorithm>
using namespace std;
int n = 6;
int a[50] = {0, 1, 5, 7, 9, 23, 60};
int main() {
cout<<"a数组从a[1]到a[n]这n个数中第一个大于9的数的地址为"<<upper_bound(a+1,a+n+1,9)<<endl;
cout<<"a数组从a[1]到a[n]这n个数中第一个大于9的数的位置为"<<upper_bound(a+1,a+n+1,9)-a<<endl;
cout<<"a数组从a[1]到a[n]这n个数中第一个大于10的数的位置为"<<upper_bound(a+1,a+n+1,10)-a<<endl;
cout<<"a数组从a[0]到a[n-1]这n个数中第一个大于9的数的位置为"<<upper_bound(a,a+n,9)-a<<endl;
cout<<"a数组从a[1]到a[n]这n个数中第一个大于13的数的位置为"<<upper_bound(a+1,a+n+1,13)-a<<endl;
cout<<"a数组从a[1]到a[n]这n个数中第一个大于7的数的位置为"<<upper_bound(a+1,a+n+1,7)-a<<endl;
cout<<"a数组从a[1]到a[n]这n个数中第一个大于10000的数的位置为"<<upper_bound(a+1,a+n+1,10000)-a<<endl;
return 0;
}
/*
a数组从a[1]到a[n]这n个数中第一个大于9的数的地址为0x46a054
a数组从a[1]到a[n]这n个数中第一个大于9的数的位置为5
a数组从a[1]到a[n]这n个数中第一个大于10的数的位置为5
a数组从a[0]到a[n-1]这n个数中第一个大于9的数的位置为5
a数组从a[1]到a[n]这n个数中第一个大于13的数的位置为5
a数组从a[1]到a[n]这n个数中第一个大于7的数的位置为4
a数组从a[1]到a[n]这n个数中第一个大于10000的数的位置为7
*/扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。