二分法
二分的三种题型
根据特定值查找的
查找特定值的意思是说，判断
nums[mid]时，只需要用到nums[mid]这个值，而不需要用到其周围左右的值。具体包含以下两类：- 查找特定
target
- 查找
teaget左/右边界
经典题型1095
查找特定target：
查找
teaget左/右边界：
根据左右的特征进行二分减治
这类题目一般没法根据判断 nums[mid] 和 target 的大小来缩减搜索空间，主要根据数组本身的特征进行分段。
二分法的思想是减治，就是说每一次访问都可以使得搜索空间减半，所以核心思路是找 左右两段不一样的根本区别所在，然后由特征判断抛弃哪一段，即缩小搜索空间。最常见的特征为变化趋势，所以经常根据变化趋势进行查找，典型的题目旋数组相关题目。
根据变化趋势查找是指，根据数组中元素的上升或者下降趋势来查找峰值或者低谷值。这类题目一般是要通过 nums[mid] >nums[mid+1]来判断left 和right的走向。或者说需要访问数组中当前索引及其直接右邻居索引的元素或条件。保证查找空间在每一步中至少有 2 个元素。当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。
模板
class Solution: def findPeakElement(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left < right: mid = left + (right - left) // 2 if nums[mid] < nums[mid + 1]: left = mid + 1 else: right = mid return left
right = len(nums) - 1 以及 while left < right 保证了不管何时 mid 和mid+ 1 均可以取到。如果需要查找空间在每一步中至少需要k个元素，那么right = len(nums) - k。这样mid 和 mid + k 才总不会越界。
经典题型
在答案集上进行二分
根据答案进行二分判断，以缩减可能的答案空间。
看到最大，最少，极大极小，极小极大，都先尝试着用二分法
经典题目:
二分速通
完整笔记参见 二分法
寻找左边界/右边界；有一个明确的 target 与 nums[mid] 对比；l ≤ r
- 根据左右特征进行减治；nums[mid] 与nums[mid+1] or nums[r] 对比； l < r
- 猜答案；在答案集上二分，一般是找左边界 or 右边界; l≤ r
Tips
- 一类经典的题目：找第k大或第 k小。这类题目优先想堆，如果堆没法实现，那么就尝试二分法。
- 旋转数组的题目，让
mid和right比较，以判断mid是在做半段还是右半段，然后再分别做细致的判断
- 按变化趋势查找一般是
right = mid。这是由于当left = right - 1时，mid = left，且搜索空间为左闭右开
- 当需要用到mid + 1 及 mid - 1 的时候，搜索空间应该不包含数组的起止，即left, right 指针不设置在起始和结束位置。
- 对于 while left ≤ right, 搜索空间为左右闭合的，所以判断好后可以直接，left = mid + 1 right = mid - 1； 而对于 while left < right 的， 搜索空间为左闭右开的，所以判断好后，right 只能是 right = mid。
- 二分法的思想是减治，每一次访问都可以使得搜索空间减半。所以核心思路是找 左右两段不一样的根本区别所在，然后由特征判断抛弃哪一段。
- 对于没有明确数组大小的，采用倍增的思想，先找搜索空间的右边界right。例如题目447 · 在大数组中查找 - LintCode
- 二分思想扩展：找喷香水的人，把教室的所有人一分为2，放到两个教室，然后一段时间后没有香味的教室里面的所有人即可排除了。经典二分思想，类似的还有，图书馆门口，排除没有借阅记录的数据。
记录
2021年11月20日 | 峰值类型题目，因为要比较mid 和mid+1，所以条件为left < right，这样mid+1永远能取到 | 162 |
2021年11月21日 | 二分法的思想是减治，所以核心思路是找 左右两段不一样的根本区别所在，然后由特征判断抛弃哪一段。 | 540 |
ㅤ | 推荐题目：875，33，658，69，34，540，528 | ㅤ |
2022年1月21日 | 看到极大极小、极小极大、最大、最小 都先尝试着二分。 | ㅤ |
ㅤ | 推荐题目：34, 162, 1095, 528，540， 153， 154 | ㅤ |