# 7. 练习
提示：这些问题都不应该当做模板问题来看待，逻辑严密的分析与思考是更关键的。我们针对这些问题都提供了题解，重点分析了应该如何思考，讲解了如何编写正确的代码，希望能够对大家有所帮助。
# 题型一：二分下标（在数组中查找符合条件的元素的下标）
一般而言这个数组是有序的，也可能是半有序的（旋转有序数组或者山脉数组）。
| 题目 | 题解 | 说明 |
|---|---|---|
| 704. 二分查找（简单） (opens new window) | 二分查找的最原始问题，使用本题解介绍的方法就要注意，需要后处理。 | |
| 34. 在排序数组中查找元素的第一个和最后一个位置（中等） (opens new window) | 文字题解 (opens new window)、视频题解 (opens new window) | 查找边界问题。 |
| 33. 搜索旋转排序数组（中等） (opens new window) | 文字题解 (opens new window) | 利用局部单调性，逐步缩小搜索区间（其它问题类似）。 |
| 81. 搜索旋转排序数组 II（中等） (opens new window) | 文字题解 (opens new window) | |
| 153. 寻找旋转排序数组中的最小值（中等） (opens new window) | 文字题解 (opens new window) | |
| 154. 寻找旋转排序数组中的最小值 II（中等） (opens new window) | 文字题解 (opens new window) | |
| 300. 最长上升子序列（中等） (opens new window) | 文字题解 (opens new window)。 | 特别经典的一道「动态规划」，二分查找的思路基于「动态规划」的状态定义得到，代码很像第 35 题。 |
| 275. H指数 II（中等） (opens new window) | 文字题解 (opens new window) | 这个问题题目的描述让人迷惑，可以跳过不做。 |
| 852. 山脉数组的峰顶索引（简单） (opens new window) | 利用局部单调性，逐步缩小搜索区间。 | |
| 1095. 山脉数组中查找目标值（中等） (opens new window) | 文字题解 (opens new window)、视频题解 (opens new window) | |
| 4. 寻找两个有序数组的中位数（困难） (opens new window) | 文字题解 (opens new window)、视频题解 (opens new window) | |
| 658. 找到 K 个最接近的元素（中等） (opens new window) | 文字题解 (opens new window) | 这个问题二分的写法需要做复杂的分类讨论，可以放在以后做。 |
# 题型二：二分答案（在一个有范围的区间里搜索一个整数）
定位一个有范围的整数，这件事情也叫「二分答案」或者叫「二分结果」。如果题目要求的是一个整数，这个整数有明确的范围，可以考虑使用二分查找。
事实上，二分答案是我们最早接触的二分查找的场景。「幸运 52」里猜价格游戏，就是「二分查找」算法的典型应用：先随便猜一个数，如果猜中，游戏结束。如果猜大了，往小猜；如果猜小了，往大猜。
| 题目 | 题解 | 说明 |
|---|---|---|
| 69. 平方根（简单） (opens new window) | 文字题解 (opens new window) | 在一个整数范围里查找一个整数，也是二分查找法的应用场景。 |
| 287. 寻找重复数（中等） (opens new window) | 文字题解 (opens new window) | 在一个整数范围里查找一个整数。这个问题二分查找的解法很反常规（不应该用时间换空间，这么做太傻了），知道即可。 |
| 374. 猜数字大小（简单） (opens new window) | 文字题解 (opens new window) | |
| 1300. 转变数组后最接近目标值的数组和 (opens new window) | 文字题解 (opens new window) |
# 题型三：二分答案的升级版：判别条件需要遍历数组
说明：这里给出的问题解法都一样，会一题等于会其它题。问题的场景会告诉我们：目标变量和另一个变量有相关关系（一般是线性关系），目标变量的性质不好推测，但是另一个变量的性质相对容易推测（满足某种意义上的单调性）。这样的问题的判别函数通常会写成一个函数的形式。
这一类问题可以统称为「 最大值极小化 」问题，最原始的问题场景是木棍切割问题，这道题的原始问题是「力扣」第 410 题（分割数组的最大值（困难） (opens new window)）。
思路是这样的：
- 分析出题目要我们找一个整数，这个整数有范围，所以可以用二分查找；
- 分析出 单调性，一般来说是一个变量
a的值大了，另一个变量b的值就变小，而「另一个变量的值」b有限制，因此可以通过调整a的值达到控制b的效果； - 这一类问题的题目条件一定会给出 连续、正整数 这样的关键字。如果没有，问题场景也一定蕴含了这两个关键信息。
以下给出的问题无一例外。