STL系列(二) 二分查找
STL系列(二)二分查找
函数:binary_search
- 内容里如有未知文章中未提到的函数引用请查看上一篇文章STL系列(一)sort用法
- 本期内容会出现大量相似但不相同的话,认真阅读,注意对比,加深记忆,不要觉得内容重复而心烦
- 注意加粗语句
- 有疑问留言 or 评论
用法一(基本查找)
内容:
binary_search( 数组名 + n1, 数组名 + n2, 值 )
n1和n2都是 int 类型的表达式 , 可以包含变量
如果n1 = 0,则 + n1 可以不写
查找区间为下标范围为[n1,n2)的元素, 下标为n2的元素不在查找区间内
在该区间内查找"等于"值的元素, 返回值为true(找到) 或false(没找到)
"等于"的含义: a 等于 b <==> a < b和b < a都不成立范例:
int a[] = { 12,45,3,98,21,7 };
sort(a, a + 6);
Print(a, 6); //结果: 3,7,12,21,45,98
cout << "Result : " << binary_search(a, a + 6, 12) << endl; //Result : 1
cout << "Result : " << binary_search(a, a + 6, 77) << endl; //Result : 0- 在使用STL二分查找前要先用sort排序;
用法二 (自定义排序规则查找)
内容:
在用自定义排序规则排好序的 , 元素为任意的T类型得数组进行二分查找
binary_search(数组名 +n1 , 数组名 + n2 , 值 , 排序规则结果名() );n1和n2都是int类型得表达式,可以包含变量
如果 n1 = 0 , 则 + n1可以不写
查找区间为下标范围[n1,n2)的元素 , 下标为n2的元素不在查找区间内
在该区间内查找"等于"值的元素, 返回值为true(找到) 或false(没找到)
*查找时的排序规则,必须和排序时的规则一致!
"等于"的含义: a 等于 b <==> "a必须在b前面"和"b必须在a前面"都不成立重要的事多次强调加深印象! 不是水文章!
范例:
int a[] = { 12,45,3,98,21,7 };
sort(a, a + 6, Rule1()); //按从小到大排序(此处使用Rule1规则进行排序)
Print(a, 6); // 21,12,3,45,7,98
cout << "Result : " << binary_search(a, a + 6, 7) << endl; //Result : 0
cout << "Result : " << binary_search(a, a + 6, 8, Rule1()) << endl; //Result : 1
return 0;上面代码第4行为错误代码
此处编译器返回值为0并不是意味着没查到!
binary_search()二分查找规则必须与排序规则一致, 否则返回值 没有意义
完整代码:(包含自定义函数)
#include
#include
#include
using namespace std;
struct Rule1 {
bool operator()(const int& a1, const int& a2)const {
return a1 % 10 < a2 % 10;
}
};
void Print(int a[], int size);
int main() {
int a[] = { 12,45,3,98,21,7 };
sort(a, a + 6);
Print(a, 6);
cout << "Result : " << binary_search(a, a + 6, 12) << endl;
cout << "Result : " << binary_search(a, a + 6, 77) << endl;
sort(a, a + 6, Rule1());//按从小到大排序
Print(a, 6);
cout << "Result : " << binary_search(a, a + 6, 7) << endl;
cout << "Result : " << binary_search(a, a + 6, 8, Rule1()) << endl;
return 0;
}
void Print(int a[], int size) {
int i;
for (i = 0; i < size - 1; i++) {
cout << a[i] << ",";
}
cout << a[i];
cout << endl;
}函数lower_bound
用法一(查找下界)
在对元素类型为 T 的从小到大排好序的基本数据类型中进行查找
T * lower_bound(数组名 + n1 , 数组名 + n2 , 值);返回一个指针 T * p;
*p 是查找区间里下标最小的,大于等于"值"的元素. 如果找不到, p 指向下标为n2 的元素
注意:n2不在查询范围内哦!
范例:
int a[NUM] = { 12,5,3,5,98,21,7 };
sort(a, a + NUM);
Print(a, NUM); // 结果: 3,5,5,7,12,21,98
int* p1 = lower_bound(a, a + NUM, 5); //范围整个数组,p1指向下标最小的 大于等于5的元素
cout << " p1指向的内容:"<< *p1 << " 下标:" << p1 - a << endl; // 结果:5,1用法二(自定义规则查找下界)
在对元素类型为 T ,按照自定义排序规则排好序的数组中进行查找
T * lower_bound(数组名 + n1 , 数组名 + n2 , 值 , 排序规则结构名());返回一个指针 T * p;
*p 是查找区间里下标最小的,按自定义排序规则 , 可以 排在"值"后面的元素. 如果找不到,p指向下标为n2的元素
注意:n2不在查询范围内哦!
范例:
int a[NUM] = { 12,5,3,5,98,21,7 };
sort(a, a + NUM, Rule1());
Print(a, NUM); // 结果 :21,12,3,5,5,7,98
cout << *lower_bound(a, a + NUM, 16, Rule1()) << endl; // 结果 : 7 (输出元素值)
cout << lower_bound(a, a + NUM, 25, Rule1()) - a << endl; // 结果 : 3 (输出下标值)后面内容可以自己试着分析原因
函数upper_bound
用法一(查找上界)
内容:
在元素类型为 T 的从小到大排好序的基本类型得数组中进行查找
T * upper_bound(数组名 + n1 , 数组名 + n2 , 值);返回一个指针 T * p;
*p 是查找区间里下标最小的, 大于"值"的元素. 如果找不到, p指向下标为n2 的元素
范例:
int a[NUM] = { 12,5,3,5,98,21,7 };
sort(a, a + NUM);
Print(a, NUM); // 结果: 3,5,5,7,12,21,98
int* p2 = upper_bound(a, a + NUM, 5); //范围整个数组,p2指向下标最小的 大于5的元素
cout << *p2 << endl; // 结果:7
cout << *upper_bound(a, a + NUM, 13) << endl;//查找大于13的下标最小的元素值 结果 :21用法二(自定义规则查找上界)
内容:
在元素为任意的T类型 , 按照自定义排序规则排好序的数组中进行查找
T * upper_bound(数组名 + n1 , 数组名 + n2 , 值 , 排序规则结构体());返回一个指针 T * p;
*p 是查找区间内下标最小的, 按自定义排序规则, **必须 **排在 “值” 后面的元素 . 如果找不到 ,p指向下标为n2的元素
范例:
int a[NUM] = { 12,5,3,5,98,21,7 };
sort(a, a + NUM, Rule1());
Print(a, NUM); // 结果 :21,12,3,5,5,7,98
cout << *lower_bound(a, a + NUM, 16, Rule1()) << endl; // 结果 : 7 (输出元素值)
cout << lower_bound(a, a + NUM, 25, Rule1()) - a << endl; // 结果 : 3 (输出下标值)
cout << upper_bound(a, a + NUM, 18, Rule1()) - a << endl; // 结果 : 7 (无意义)(个位数大于8无法找到)(找不到时返回终点元素)
if (upper_bound(a, a + NUM, 18, Rule1()) == a + NUM)
cout << "not found" << endl; // ==>not found;
cout << *upper_bound(a, a + NUM, 5, Rule1()) << endl; // 结果 : 7 (自己想想原因)
cout << *upper_bound(a, a + NUM, 4, Rule1()) << endl; // 结果 : 5完整代码:
#include
#include
#include
#define NUM 7
using namespace std;
struct Rule1 {
bool operator()(const int& a1, const int& a2)const {
return a1 % 10 < a2 % 10;
}
};
void Print(int a[], int size);
int main() {
int a[NUM] = { 12,5,3,5,98,21,7 };
sort(a, a + NUM);
Print(a, NUM); // 结果: 3,5,5,7,12,21,98
int* p1 = lower_bound(a, a + NUM, 5); //范围整个数组,p1指向下标最小的 大于等于5的元素
cout << " p1指向的内容:"<< *p1 << " 下标:" << p1 - a << endl; // 结果:5,1
int* p2 = upper_bound(a, a + NUM, 5); //范围整个数组,p2指向下标最小的 大于5的元素
cout << *p2 << endl; // 结果:7
cout << *upper_bound(a, a + NUM, 13) << endl;//查找大于13的下标最小的元素值 结果 :21
sort(a, a + NUM, Rule1());
Print(a, NUM); // 结果 :21,12,3,5,5,7,98
cout << *lower_bound(a, a + NUM, 16, Rule1()) << endl; // 结果 : 7 (输出元素值)
cout << lower_bound(a, a + NUM, 25, Rule1()) - a << endl; // 结果 : 3 (输出下标值)
cout << upper_bound(a, a + NUM, 18, Rule1()) - a << endl; // 结果 : 7 (无意义)(个位数大于8无法找到)(找不到时返回终点元素)
if (upper_bound(a, a + NUM, 18, Rule1()) == a + NUM)
cout << "not found" << endl; // ==>not found;
cout << *upper_bound(a, a + NUM, 5, Rule1()) << endl; // 结果 : 7 (自己想想原因)
cout << *upper_bound(a, a + NUM, 4, Rule1()) << endl; // 结果 : 5
return 0;
}
void Print(int a[], int size) {
int i;
for (i = 0; i < size - 1; i++) {
cout << a[i] << ",";
}
cout << a[i];
cout << endl;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/02/02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
