寒假week1---二分查找(二分枚举)
2024-08-30 00:57:22
寒假week1---二分查找(二分枚举)
1.适用条件:要查找(枚举)的集合有序 && 查找(枚举)的“条件”具有单调性
2.什么是“条件”:
example:
1.给定一个有序数组,从中查找数字7的下标。条件是:这个数字等于7.
2.给定一个有序数组,从中查找满足函数f(x)<99的数字的下标。条件是:f(x)<99.
3.什么是“满足条件”:
在上述例1中,所有等于7的数字都是满足条件的,例2中所有f(x)<99的x也都是满足条件的。
由此可见,最理想的情况是满足条件的元素只有一个,考虑实际情况,满足条件的元素也可能不存在或者存在多个。在这种情况下,往往题目中会有特殊的要求,譬如找到所有满足条件元素下标最大的,或者如果不存在满足条件的元素找到小于它并且下标最接近的。参考http://blog.csdn.net/int64ago/article/details/7425727
4.什么是“单调”:
顾名思义,条件的定义依赖与一个单调的函数,不管是单调递增还是单调递减都可以用二分查找。
5.为什么要学二分查找:
这是ACM/ICPC简单题目的常见套路。(微笑)
6.需要做哪些题目:
刷题list会持续更新,大家也可以自己找二分查找的题目,在VJ的contest按照比赛的titile查找关键词“二分”(以后别的专题也可这样查找题目,不赘述)
刷题list网址:https://github.com/ttbond/OUC-/blob/master/week1
最新文章
- 【我是老中医】VMware在win8.1下开Ubuntu提示”内部错误";解决方案
- vi 使用入门
- ios UITextView 计算文字内容大小
- MySQL乱码解决办法
- GCD,用同步/异步函数,创建并发/串行队列
- js获取页面高度赋值给div
- telnet的使用
- light oj 1248 第六周E题(期望)
- mybatia的mypper.xml文件,参数类型为map,map里有一个键值对的值为数组,如何解析,例子可供参考,接上文,发现更简便的方法,不必传数组,只需传字符串用逗号隔开即可
- 函数 setjmp, longjmp, sigsetjmp, siglongjmp
- js的严格模式详解
- web服务器之nginx和apache的区别
- js倒计时一分钟
- MapRdeuce&Yarn的工作机制(YarnChild是什么)
- CentOS配置VSFTP服务
- 将本地分支push到远程分支
- Docker配置阿里云加速地址
- Dubbo在开发中的一些常用配置
- FFmpeg(13)-创建OpenSLES混音器CreateOutputMix初始化
- Django(一)创建和启动项目