C++ 折半查找之 lower_bound 和 upper_bound
1. lower_bound
1.1 基本用法
含义：满足下界的就 pass，找到第一个不满足下界的元素，即第一个 >= 下界 的元素， 返回其迭代器
专业成都网站建设公司，做排名好的好网站，排在同行前面，为您带来客户和效益!成都创新互联为您提供成都网站建设，五站合一网站设计制作，服务好的网站设计公司，成都网站建设、网站设计负责任的成都网站制作公司!
这里的下界 为 7, 所以是这样理解，凡是小于 7 的都是满足 下界，都会 pass，直到找到 >= 7 的元素，然后返回这个元素的迭代器。
vectorv = {1,4,5,2,3,6,8,12,9,7,11,10};
auto it = lower_bound(v.begin(), v.end(), 7);
cout<< *it<< endl; // 8
注意这里返回的是 8 ，也就是第一个 >= 7 的元素， 而不是最小的 >= 7 的元素
所以 lower_bound 的含义是，返回序列中第一个 >= 下界的元素 的迭代器，元素 7 不是 第一个 >= 7 的元素
1.2 注意点
使用 lower_bound 时候 的注意点
- lower_bound 需要满足 所有元素 ”有序“, 但是这里的有序不是一定要 单调递增 或者 单调递减，而是序列中的 前部分 都是 小于 下界，后部分 都是 大于等于 下界，但是 前部分 和 后部分 各自内部 是 可以 乱序 的。
参考 C++ lower_bound()函数用法详解
下面验证这个点
vectorv = {1,2,100,16,18,17,11,13,81,115,9,16,13,15,19 }; // size()=15, v[7]=13
auto it = lower_bound(v.begin(), v.end(), 7);
cout<< *it<< endl; // 100
似乎这里按照往常 折半 的思路，应该第一个比较的元素是中间的元素 13 ，应该直接返回 13，因为 13 已经满足 大于等于下界了，但是按照 lower_bound() 的含义，必须是第一个 >= 下界的元素，所以 13 未必是 第一个，因此，可以认为此时
left指针=0，v[0]=1
right指针=7, v[7]=13
然后继续在 v[0]~v[7] 之间继续 折半 搜索下去
整个过程大概是这样，下界 = 7
| 查找范围 | 中间值 | 新范围 |
|---|
| v[0]~v[14] | v[7]=13 | v[0]~v[7] |
| v[0]~v[7] | v[3]=16 | v[0]~v[3] |
| v[0]~v[3] | v[1]=2 | v[2]~v[3] |
| v[2]~v[3] | v[2]=100 | v[2]~v[2] |
最终返回 v[2]=100 的迭代器
再次验证
vectorv = {4,3,1,2,100,16,18,17,11,13,81,115,9,16,13,15,19 };
auto it = lower_bound(v.begin(), v.end(), 7);
cout<< *it<< endl; // 100
1.3 错误使用 lower_bound 的情况
合理的序列：前部分< 下界，后部分 >= 下界
假如前部分是包含了 >= 下界 的元素，此时就不能使用 lower_bound() ，因为结果是错误的
vectorv = {101,4,3,1,2,100,16,18,17,11,13,81,115,9,16,13,15,19 };
auto it = lower_bound(v.begin(), v.end(), 7);
cout<< *it<< endl; // 100
所以 lower_bound 查找的范围必须满足
- lower_bound 需要满足 所有元素 ”有序“, 但是这里的有序不是一定要 单调递增 或者 单调递减 ，而是序列中的 前部分 都是 小于< 下界，后部分 都是 大于等于< 下界，但是 前部分 和 后部分 各自内部 是 可以 乱序 的。
1.4 自定义比较函数
lower_bound 支持 自定义的 比较规则
序列中的 前部分满足 cmp (即 cmp 返回 true)，后部分 不满足 cmp， 返回 false
找到第 1 个返回 false 的元素
bool cmp(const int& e, const int& val)
{return e< val; // val 始终等于 7
}
int main()
{//找到一个 让 cmp 返回 false 的元素的下标, 即 第 1 个 >= 7 的元素
vectorv = {4,3,1,2,100,16,18,17,11,13,81,115,9,16,13,15,19 };
auto it = lower_bound(v.begin(), v.end(), 7,cmp);
// 等效 auto it = lower_bound(v.begin(), v.end(), 7);
cout<< *it<< endl; // 100
return 0;
}
如上，cmp 的 **第二个参数 val **始终等于 7 ( lower_bound 中的 第 3 个参数 值 )，
- 凡是 满足 cmp 的元素值 ( 即cmp 返回 true )，认为都是满足< 下界的，都会 pass
- 凡是 cmp 返回 false的 ，就是 >= 下界，lower_bound 返回 序列 中 第一个 让 cmp 不成立的元素
注意，序列中的 前部分 应该是 满足 cmp (即 cmp 返回 true)，后部分 不满足 cmp， 返回 false，即 前 T 后 F
否则可能会出问题
比如下面 2 种情况，前 F 后 T，恰好相反
bool cmp(const int& e, const int& val)
{return e< val;
}
//找到一个 让 cmp 返回 false 的元素的下标, 即 第 1 个 >= 15 的元素
vectorv = {100,16,18,17,11,13,10,5,1,2,3,5,6,4,3,1,2 };
auto it = lower_bound(v.begin(), v.end(), 15,cmp);
if (it == v.end())
cout<< "未找到满足条件的元素"<< endl;
else
cout<< *it<< endl;
// 输出 未找到满足条件的元素
中间元素 v[8]=1, 导致后续在 v[9]~v[16] 搜索，而 v[9]~v[16] 不存在 >= val 的元素
没有找到 v[0]=100
bool cmp(const int& e, const int& val)
{return e< val;
}
//找到一个 让 cmp 返回 false 的元素的下标, 即 第 1 个 >= 15 的元素
vectorv = {100,16,18,17,21,23,19,51,81,32,32,5,6,4,3,1,2 };
auto it = lower_bound(v.begin(), v.end(), 15,cmp);
if (it == v.end())
cout<< "未找到满足条件的元素"<< endl;
else
cout<< *it<< endl;
// 输出 100
中间元素 v[8]=81, 导致后续在 v[0]~v[8] 搜素，能够找到 v[0]=100
主要还是看第一次 中间的 那个元素
所以，最好还是满足
- 序列中的 前部分满足 cmp (即 cmp 返回 true)，后部分 不满足 cmp， 返回 false
再次测试
让 序列中的 前部分满足 cmp (即 cmp 返回 true)，后部分 不满足 cmp， 返回 false
lower_bound 返回第一个 让 cmp 返回 false 的元素的 迭代器
测试1第 1 个< 20 的元素
bool cmp(const int& e, const int& val)
{return e >= val;
}
int main()
{//找到一个 让 cmp 返回 false 的元素的下标, 即 第 1 个< 20 的元素
vectorv = {31,88,41,25,20,22,20,8,12,9,7,11,10};
auto it = lower_bound(v.begin(), v.end(), 20,cmp);
if (it == v.end())
cout<< "未找到满足条件的元素"<< endl;
else
cout<< *it<< endl; // 8
return 0;
}
测试2第 1 个 无法 被 5 整除 的元素
bool cmp(const int& e, const int& val)
{return (e % val)==0;
}
int main()
{//找到一个 让 cmp 返回 false 的元素的下标, 即 第 1 个 无法 被 5 整除 的元素
vectorv = {30,80,40,20,20,25,35,80,12,9,7,11,5};
auto it = lower_bound(v.begin(), v.end(), 5,cmp);
if (it == v.end())
cout<< "未找到满足条件的元素"<< endl;
else
cout<< *it<< endl; // 12
return 0;
}
测试3当然也可以使用 lambda 表达式
int main()
{//找到一个 让 lambda 返回 false 的元素的下标, 即 第 1 个 无法被 5 整除 的元素
vectorv = {30,80,40,20,20,25,35,80,12,9,7,11,5};
//auto it = lower_bound(v.begin(), v.end(), 5,cmp);
auto it = lower_bound(v.begin(), v.end(), 5, [](const int& e, const int& val) {return (e % val) == 0;});
if (it == v.end())
cout<< "未找到满足条件的元素"<< endl;
else
cout<< *it<< endl; // 12
return 0;
}
2. upper_bound
在 windows vs2019 环境下, upper_bound 需要 #include ，但是 lower_bound 不需要
2.1 基本用法
不使用自定义函数的情况下
测试1lower_bound 返回 第一个 >= 下界 的元素, upper_bound 返回 第一个 >下界 的元素
vectorv = {4,3,1,2,9,100,16,18,17,11,13,81,115,9,16,13,15,19 };
// 找到 第一个 >= 9 的元素
auto it1 = lower_bound(v.begin(), v.end(), 9);
if (it1 == v.end())
cout<< "lower_bound 未找到满足条件的元素"<< endl;
else
cout<< *it1<< endl; // 9
// 找到 第一个 >9 的元素
auto it2 = upper_bound(v.begin(), v.end(), 9);
if (it2 == v.end())
cout<< "upper_bound 未找到满足条件的元素"<< endl;
else
cout<< *it2<< endl; // 100
测试2lower_bound 返回第一个 >= 下界 的元素, upper_bound 返回第一个 >下界 的元素
int main()
{vectorv = {4,3,1,2,9 };
// 找到 第一个 >= 9 的元素
auto it1 = lower_bound(v.begin(), v.end(), 9);
if (it1 == v.end())
cout<< "lower_bound 未找到满足条件的元素"<< endl;
else
cout<< *it1<< endl; // 9
// 找到 第一个 >9 的元素
auto it2 = upper_bound(v.begin(), v.end(), 9);
if (it2 == v.end())
cout<< "upper_bound 未找到满足条件的元素"<< endl;
else
cout<< *it2<< endl;
// upper_bound 未找到满足条件的元素
return 0;
}
2.2 自定义比较函数
注意，upper_bound 中 cmp 的 **第1个参数 val **始终等于 9 ( upper_bound 中的 第 3 个参数 值 )，
- 序列中的 前部分不满足 cmp (即 cmp 返回 false )，后部分 满足 cmp， 返回 true
返回第一个 满足 cmp (返回true) 的 元素 的迭代器
测试3找到第一个大于 9 的元素，返回其迭代器
bool cmp2(const int& val, const int& e)
{return valvectorv = {4,3,1,2,9,100,16,18,17,11,13,81,115,9,16,13,15,19 };
// 找到第一个 >9 的元素, 即 a[5]=100
auto it2 = upper_bound(v.begin(), v.end(), 9,cmp2);
if (it2 == v.end())
cout<< "upper_bound 未找到满足条件的元素"<< endl;
else
cout<< *it2<< endl; // 100
return 0;
}
测试4找到第一个能被 5 整除 的元素，返回其迭代器
bool cmp3(const int& val, const int& e)
{return (e % val) == 0;
}
int main()
{vectorv = {4,19,26,34,17,29,40,10,15,30,20 };
auto it2 = upper_bound(v.begin(), v.end(), 5,cmp3);
if (it2 == v.end())
cout<< "upper_bound 未找到满足条件的元素"<< endl;
else
cout<< *it2<< endl; // 40
return 0;
}
2.3 upper_bound 和 lower_bound 的区别
auto it1 = lower_bound(v.begin(), v.end(), val,cmp1);
auto it2 = upper_bound(v.begin(), v.end(), val,cmp2);
| lower_bound | upper_bound |
|---|
| 无自定义比较函数 | 返回第一个 >= 下界 的元素 | 返回第一个 >下界 的元素 |
| 使用自定义比较函数 | 返回第一个 false 的元素
val 是 自定义函数 中的第 2 个参数
e< val | 返回第一个 true 的元素
val 是自定义函数中的 第 1 个参数
val< e |
| 序列的前部分满足 cmp (返回 true)
后部分不满足 cmp (返回 false)
找到第 1 个 false 的元素 | 序列的前部分不满足 cmp (返回 false)
后部分满足 cmp (返回 true)
找到第 1 个 true 的元素 |
关于 val 在 lower_bound 的 cmp 中 是第 2 个参数 ，在 upper_bound 的 cmp 中 是 第 1 个参数
简单的记忆：比较的时候都是用 小于<
lower 就是 小于 ，即小于 val , e< val，所以 val 是 第 2 个参数
upper 就是 大于 ，即大于 val , val< e，所以 val 是 第 1 个参数
测试4lower_bound 和 upper_bound 都是用 自定义函数
bool cmp1(const int& e, const int& val)
{return e< val;
}
bool cmp2(const int& val, const int& e)
{return val< e;
}
int main()
{vectorv = {4,3,1,2,9,100,16,18,17,11,13,81,115,9,16,13,15,19 };
auto it1 = lower_bound(v.begin(), v.end(), 9,cmp1);
// 第一个让 cmp1 返回 false 的元素, 即第一个 >= 9 的元素
if (it1 == v.end())
cout<< "lower_bound 未找到满足条件的元素"<< endl;
else
cout<< *it1<< endl; // 9
cout<< endl<< endl<< endl;
// 第一个让 cmp2 返回 true 的元素, 即第一个 >9 的元素
auto it2 = upper_bound(v.begin(), v.end(), 9,cmp2);
if (it2 == v.end())
cout<< "upper_bound 未找到满足条件的元素"<< endl;
else
cout<< *it2<< endl; // 100
return 0;
}
upper_bound 将 cmp 中改成 >= ， 即得到和 lower_bound 一样的结果
bool cmp2(const int& val, const int& e)
{//cout<< val<< '\t'<< e<< endl;
return val<= e;
}
int main()
{vectorv = {4,3,1,2,9,100,16,18,17,11,13,81,115,9,16,13,15,19 };
// 第一个让 cmp2 返回 true 的元素, 即第一个 >= 9 的元素
auto it2 = upper_bound(v.begin(), v.end(), 9,cmp2);
if (it2 == v.end())
cout<< "upper_bound 未找到满足条件的元素"<< endl;
else
cout<< *it2<< endl; // 9
return 0;
}
测试5lower_bound 和 upper_bound 都找到第一个 能被 5 整除 的元素，返回其迭代器
bool cmp1(const int& e, const int& val)
{return (e % val) != 0;
}
bool cmp2(const int& val, const int& e)
{return (e % val) == 0;
}
int main()
{vectorv = {4,19,26,34,17,29,40,10,15,30,20 };
// 寻找第 1 个让 cmp1 为 false的元素, 即 第 1 个 5 的倍数
// 非 5 的倍数,cmp1 为true, 直接 pass
// 遇到第一个 5 的倍数, cmp1 为 false， 返回该元素
auto it1 = lower_bound(v.begin(), v.end(), 5, cmp1);
if (it1 == v.end())
cout<< "lower_bound 未找到满足条件的元素"<< endl;
else
cout<< *it1<< endl; // 40
cout<< endl<< endl<< endl;
// 寻找让 cmp2 返回 true 的第 1 个元素的迭代器, 也就是找到 第 1 个 5 的倍数
auto it2 = upper_bound(v.begin(), v.end(), 5,cmp2);
if (it2 == v.end())
cout<< "upper_bound 未找到满足条件的元素"<< endl;
else
cout<< *it2<< endl; // 40
return 0;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享标题：C++折半查找之lower-创新互联
转载源于：
http://www.cdkjz.cn/article/djcces.html
