九章算法之二分法(Binary Search).pdf

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.45M 资料格式：pdf 举报版权申诉

quantbaby-10909158-16359647406154074033.pdf-第1页.png

第1页 / 共29页

quantbaby-10909158-16359647406154074033.pdf-第2页.png

第2页 / 共29页

quantbaby-10909158-16359647406154074033.pdf-第3页.png

第3页 / 共29页

quantbaby-10909158-16359647406154074033.pdf-第4页.png

第4页 / 共29页

quantbaby-10909158-16359647406154074033.pdf-第5页.png

第5页 / 共29页

quantbaby-10909158-16359647406154074033.pdf-第6页.png

第6页 / 共29页

quantbaby-10909158-16359647406154074033.pdf-第7页.png

第7页 / 共29页

quantbaby-10909158-16359647406154074033.pdf-第8页.png

第8页 / 共29页

文本预览

二分法 Binary Search 课程版本 4.0 主讲令狐冲扫描二维码关注微信/微博获取最新面试题及权威解答微信: ninechapter 微博: http://www.weibo.com/ninechapter 知乎: http://zhuanlan.zhihu.com/jiuzhang 官网: http://www.jiuzhang.com 禁止录像与传播录像，否则将追求法律责任和经济赔偿第1页

上课须知 • 课程错过不补课，也不提供任何视频 • 你才会把在两个小时内集中精力，全神贯注 • 你才会把学习放在第一位，而不是先 LoL 一把，先逛个街，先和朋友吃个饭 • 你才会获得最佳的课程体验 • 良苦用心希望同学们理解 • 不允许建私群（包括QQ群，微信群） • 在QQ群中拉人私下组群的将被踢群并不再提供QQ答疑服务 • LintCode 需要单独先注册一个账户，不要使用九章的账号密码去登陆 • LintCode 阶梯训练必须先完成上一节课的作业，才能做下一节课的作业 • 课程各类服务的有效期为一年 • LintCode阶梯训练访问权限 • QQ群答疑 • QA答疑 • 课件 • 知识点小视频禁止录像与传播录像，否则将追究法律责任和经济赔偿 Copyright © www.jiuzhang.com 第2页

新学员问题 • 新学员必读常见问题解答 • http://www.jiuzhang.com/qa/3/ • 第一节课错过了怎么办？ • 报名下一期的《九章算法班》第一节课免费试听即可 • 学员QQ群是什么？怎么加？ • 请登录官网在我的课程中查看QQ群号 • 九章的账户绑定到LintCode之后可以解除绑定么？ • 不可以 • 因此不要把你的九章账户给别人使用 • 一些老学员的 LintCode 账号绑定了其他人的九章账户是因为你以前把账号共享给了其他人 • 你可以申请新的 LintCode 账户和你现在的账户进行绑定 • LintCode 相关问题请参见：http://www.jiuzhang.com/qa/683/ 禁止录像与传播录像，否则将追求法律责任和经济赔偿第3页

Outline • 二分法基本功 • 时间复杂度小练习 • 递归与非递归的权衡 • 二分的三大痛点 • 通用的二分法模板 • 第一境界：二分位置之圈圈叉叉 Binary Search on Index - OOXX • 找到满足某个条件的第一个位置或者最后一个位置 • 第二境界：二分位置之保留一半 Binary Search on Index - Half half • 保留有解的一半，或者去掉无解的一半 • 第三境界：二分答案 Binary Search on Result • 压根看不出是个二分法！禁止录像与传播录像，否则将追求法律责任和经济赔偿第4页

Binary Search Given an sorted integer array - nums, and an integer - target. Find the any/first/last position of target in nums Return -1 if target does not exist. 禁止录像与传播录像，否则将追求法律责任和经济赔偿第5页

T(n) = T(n/2) + O(1) = O(logn) 通过O(1)的时间，把规模为n的问题变为n/2 思考：通过O(n)的时间，把规模为n的问题变为n/2？禁止录像与传播录像，否则将追求法律责任和经济赔偿第6页

Time Complexity in Coding Interview • O(1) 极少 • O(logn) 几乎都是二分法 • O(√n) 几乎是分解质因数 • O(n) 高频 • O(nlogn) 一般都可能要排序 • O(n2) 数组，枚举，动态规划 • O(n3) 数组，枚举，动态规划 • O(2n) 与组合有关的搜索 • O(n!) 与排列有关的搜索禁止录像与传播录像，否则将追求法律责任和经济赔偿第7页

独孤九剑 —— 破剑式比O(n)更优的时间复杂度几乎只能是O(logn)的二分法经验之谈：根据时间复杂度倒推算法是面试中的常用策略禁止录像与传播录像，否则将追求法律责任和经济赔偿第8页

分享到：

赞收藏

资料库

九章算法之二分法(Binary Search).pdf

相关推荐

课程资源

热门标签

最新资料