[已解决]二分求最长 上升/下降/不上升/不下降 子序列

柿子饼同学

呃主要问题是用二分法求最长上升子序列 , 下降子序列 , 不上升子序列 , 不下降子序列 时该用哪一个
如标题 , 就是不懂什么时候用 upper_bound , 什么时候用 lower_bound
并且函数第四个参数 less<int>() 和 greater<int>() 该如何用 , 求教

最佳答案

月排行榜 / 总排行榜

dolly_yos2

2022-8-10 10:55:07

柿子饼同学 发表于 2022-8-9 20:55
谢谢 , 但是问题主要是不知道求  最长 上升, 下降, 不上升, 不下降 子序列  问题中这两个函数的使用

二分查找主要是用来在辅助数组里查找要替换的目标元素的，所以应该用哪个、怎么组合取决于对辅助数组性质的要求。这个要求应该是和目标一致的，即当求最长上升子序列的时候辅助数组应该时刻是一个严格递增的序列。
基于这一点，选择就很好做了。比如要让辅助数组是不下降的，就应该允许辅助数组里有重复值出现，替换的目标就应该是第一个比当前插入值大的元素；如果是（严格）上升的，就不能有重复值，替换的目标相反就应该是第一个不小于当前插入值的元素。剩下的工作就是根据需求选用功能正确的工具函数了，只要记住 lower_bound 会把与给定的值相等的元素也算作搜索结果就可以了。

跳转到最佳答案楼层

一点点儿

在从小到大的排序数组中，

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

在从大到小的排序数组中，重载lower_bound()和upper_bound()

lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。


https://blog.csdn.net/u011008379/article/details/50725670

一点点儿

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中，

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

第四个参数为比较函数，仅写函数名即可

如果第四个参数传入less<int>(),排序数组要从小到大，和上面的效果相同

如果第四个参数传入greater<int>()，排序数组要从大到小

lower_bound( begin,end,num,greater<int>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater<int>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

dolly_yos2

这两个函数的区别主要在于 std::upper_bound 返回的迭代器指向第一个比给定值大的元素，而 std::lower_bound 则返回的是指向第一个不小于给定值的元素的迭代器。究竟应该使用哪个完全取决于需求，看是否接受相等的情况。
第四个参数是自定义比较函数，让该工具能够处理更复杂的序关系：可以传入自定义的函数（类函数）来为此函数定义要处理的数据的序关系（即告诉 upper_bound/lower_bound 什么叫小于，什么叫大于）。
std::less 和 std::greater 可以认为是为了方便提供的工具，它们直接调用目标类型上的 < 或 > 运算符进行比较，在“小于就是小于”或者“把大于当成小于”的情况下可以直接使用（在目标元素是 int 等已经定义了大于或小于关系的类型时），避免书写无意义代码。

柿子饼同学

一点点儿 发表于 2022-8-9 20:27
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的 ...

谢谢回答, 懂了
但是问题主要是不知道求  最长 上升, 下降, 不上升, 不下降 子序列  问题中这两个函数要用哪一个

柿子饼同学

dolly_yos2 发表于 2022-8-9 20:50
这两个函数的区别主要在于 std::upper_bound 返回的迭代器指向第一个比给定值大的元素，而 std::lower_boun ...

谢谢 , 但是问题主要是不知道求  最长 上升, 下降, 不上升, 不下降 子序列  问题中这两个函数的使用

aaron0919

动态规划也行

kerln888

学习了

柿子饼同学

aaron0919 发表于 2022-8-10 08:08
动态规划也行

哈哈就是因为 dp 慢才学的二分

dolly_yos2

柿子饼同学 发表于 2022-8-9 20:55
谢谢 , 但是问题主要是不知道求  最长 上升, 下降, 不上升, 不下降 子序列  问题中这两个函数的使用

二分查找主要是用来在辅助数组里查找要替换的目标元素的，所以应该用哪个、怎么组合取决于对辅助数组性质的要求。这个要求应该是和目标一致的，即当求最长上升子序列的时候辅助数组应该时刻是一个严格递增的序列。
基于这一点，选择就很好做了。比如要让辅助数组是不下降的，就应该允许辅助数组里有重复值出现，替换的目标就应该是第一个比当前插入值大的元素；如果是（严格）上升的，就不能有重复值，替换的目标相反就应该是第一个不小于当前插入值的元素。剩下的工作就是根据需求选用功能正确的工具函数了，只要记住 lower_bound 会把与给定的值相等的元素也算作搜索结果就可以了。

柿子饼同学

dolly_yos2 发表于 2022-8-10 10:55
二分查找主要是用来在辅助数组里查找要替换的目标元素的，所以应该用哪个、怎么组合取决于对辅助数组性质 ...

好的 , 就是如果严格上升 下降 , 就是 lower
不严格就是 upper
谢谢

hornwong

white_slacker

python0729

牛

kkl44stupid

666

white_slacker

desc

python0729

1molHF

学习了