信息技术大学
二分查找
数据结构与算法·面试高频 · 第 3 章 排序与查找
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
二分查找
数据结构与算法·面试高频 · 第 3 章 排序与查找
标准二分与边界模板
二分的魂是有序与折半：区间开闭、左右收缩、返回谁，一套模板定生死。
区间定义
左闭右闭或左闭右开，选定就要坚持到底
收缩
mid 偏左取防溢出，±1 不漏防死循环
返回
命中返回 mid，未命中按语义返回 -1 或 l
左右侧边界二分
找第一个和找最后一个：命中不返回继续压边，就是标准二分改两行。
左边界
命中后收缩右半，记录候选继续找更左
右边界
命中后收缩左半，同理找最右一次
应用
插入位置、值域计数、范围查询
旋转数组二分
旋转只乱一半：先判哪半有序，target 在不在里面决定去哪边。
判有序半边
mid 与端点比较，确定哪半是单调的
定向收缩
target 落在有序半边范围内则进，否则去另一边
二分答案
「最小化最大值」类问题：答案具有单调性，就把「猜答案+验证」二分。
单调性
x 可行则更大（或更小）也可行，才可二分
验证函数
check(x) 用贪心或模拟判断可行性
题型信号
最小化最大、最大化最小、至少至多
本节要点
- ✓区间定义选一坚持，边界防死循环
- ✓左右边界：命中不返回，压边继续
- ✓旋转数组：先定有序半边再收缩
- ✓二分答案：单调性加 check 验证
延伸主题：手写左右边界二分刷运货物最大化题
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1二分最容易出错的点是什么？防错习惯是什么？
参考答案边界与死循环：收缩漏 ±1、区间定义混用、mid 取整方向不对。习惯是先声明区间语义（闭或半开），每行收缩与之一致，再用长度 1、2 的样例过一遍。
2怎么判断一道题能「二分答案」？
参考答案问自己：答案变大，可行性是否单调变化？「最小的最大载荷」这类题里可行与否沿值轴单调，就能二分值域，配一个贪心 check 验证。
3浮点数二分与整数二分的区别？
参考答案浮点没有 ±1 的天然收缩，要靠精度 eps 控制循环或固定迭代次数；精度会累计误差，能转整数域二分再换算浮点就更稳。