lower_bound和upper_bound的实现和基本用法
2024-09-20 11:27:06
最近一直在学dp,但是感觉进度明显慢了很多,希望自己可以加一把劲,不要总是拖延了...
在LIS的优化中我遇到了二分查找的问题,之前也知道lower_bound和upper_bound两个函数,但是没有做一个具体的总结,在下面我会总结这两个函数的用法,也会给出这两个函数的实现代码,代码是参考c ++ Reference 里面的...
lower_bound:
这个函数的头文件为#include <algorithm>,函数的返回值为一个指向单调序列[first, last) 中第一个不小于val的元素的地址,如果不存在满足条件的
元素则返回NULL。你可以用该函数得到的指针的值减去数组开头元素的地址得到他在单调序列中的位置。
下面解释一下该函数的几个参数:lower_bound(first, last, val);
表示在有序序列[first, lase) 的所有值中,第一个不小于val的元素的地址。
下面给出我自己对于lower_bound优化后实现的代码:有错误还请多多指出...
该代码并没有返回指针,而是直接返回了下标......
int lower_bound(vector<int> &a, int val) {
int first = , last = a.size() - , mid;
while(first <= last) {
mid = last - (last - first) / ;
if(a[mid] >= val) last = mid - ;
else first = mid + ;
}
return first;
}
upper_bound
这个函数和上面的函数内容只有一点不同,他返回的是单调序列中第一个大于val的元素的地址,如果不存在满足条件的元素则返回NULL,下面再给出我自己写的版本......
int upper_bound(vector<int> &a, int val) {
int first = , last = a.size() - , mid;
while(first <= last) {
mid = last - (last - first) / ;
if(a[mid] <= val) first = mid + ;
else last = mid - ;
}
return first;
}
最新文章
- 分享篇——我的Java学习路线
- java 线程安全不线程不安全
- Titanium中调用ios组件时语言不是本地化的解决方法
- VirtualBox Win7 虚拟机 共享文件夹设置
- 基于VC的声音文件操作(一)
- HDU 5929 Basic Data Structure 模拟
- EF6调用存储过程,返回多个结果集处理
- 14.3.5.2 Deadlock Detection and Rollback 死锁检测和回滚:
- linhaifeng
- 一个简单的ruby生成器例子(用连续体Continuation实现)
- learning makefile 定义命令包
- 深入浅出的webpack构建工具---DllPlugin DllReferencePlugin提高构建速度(七)
- Java Debugging with Eclipse - Tutorial
- 使用DOS工具修复数据库
- mongodb基础学习9-分片
- 识别名人 &#183; Find the Celebrity
- spring---aop(8)---Spring AOP中optimize
- VS2013 连接 MySQL
- 修改NavigationBar的分根线颜色
- Ubuntu 下常用的命令 简略记录
热门文章
- canal 配置
- leetcode1025
- J2SE 8的流库 --- 生成流
- 深度学习原理与框架-RNN网络框架-LSTM框架 1.控制门单元 2.遗忘门单元 3.记忆门单元 4.控制门单元更新 5.输出门单元 6.LSTM网络结构
- 查看已打包app的entitlements文件内容
- 一个简单的SignalR例子
- ReactiveX 学习笔记(13)基础类型
- 【388】※ Some useful websites for learning Python
- ReultSet有什么作用和使用
- 基于Delphi的接口编程入门