二分查找
9/9/2022 二分查找
本专题是对 力扣Letbook二分查找 (opens new window) 的总结和思考。
本系列文章：
# 算法说明
书籍资料上对二分查找的描述，基本上是对有序数组进行二分查找，即前置条件是有序。但是有序其实只是二分法的特殊形式，二分法的前置条件是二段性。如果查找的条件满足二段性，就可以考虑使用二分法。
二段性也叫排他性，即 数据一分为二，形成 确定（满足或不满足）条件/可能（满足或不满足）条件。即二段中的一段，一定要能够确定满足或确定不满足条件，对另外一段不做强制性。数组有序只是二段性的特殊形式。
二段性有很多表现形式，比如经典的数组有序，对一个有序数组，找到一个分割点数值，一边一定小于该数值，另一边一定大于该数值。
# 三个模板
二分查找的时间复杂度为对数 级别，是一种时间复杂度非常好的的算法。力扣Letbook为二分查找总结了三个模板，这三个模板很好的覆盖了二分查找的几乎全部内容，其中比较常用的为模板一和模板二，最为强大的是模板二。
# 使用场景
- 模板一，用于寻找一个特定的数据，比如在一个有序数组中寻找一个特定值
- 模板二，应用范围更广，应用于夹逼寻找满足条件的一个值，比如在一个有序数组中，寻找一个满足某条件（比如大于数组中的某一个值）的值，或在一个无重复数的数组中寻找到一个峰值（可能有多个峰值）
- 模板三，是模板二的特殊形式，当第一个元素和最后一个元素无法直接访问时，考虑使用
一般来说，模板一为二分法的基础版；模板二最为强大，覆盖的场景更多，功能更强，堪称二分法中的瑞士军刀；模板三使用场景较少，一般都可以用模板二来代替。
# 代码
二分查找代码一般由三个主要部分组成：
预处理 —— 如果集合未排序，则进行排序，即集合需要满足二段性。
二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
后处理 —— 在剩余空间中确定可行的候选者，即在满足循环条件退出时的情况处理。
# 对应区间
模板一，[left, right]，左闭右闭区间模板二，[left, right)，左闭右开区间模板三，**(left, right)，左开右开区间**
# 关于区间
之前对三个模板的理解是对应三个区间，经过多次的学习深入的思考，其实并不是。模板跟区间并没有绝对的对应的关系，核心取决与mid是否属于下一个符合题意的区间。
- 模板一，代码为
left = mid + 1; right = mid - 1，此时mid 已经判断过，不符合要求，因此不会再在左区间或右区间里 - 模板二，代码为
left = mid + 1;right = mid;或，一般来说是解决 一定不是答案/可能是答案的问题，即mid存在可能是答案的情况left = mid; right = mid - 1;left = mid + 1;，此时mid已经不符合答案要求，因此需要将 mid 移除区间right = mid;，此时mid还符合答案要求，可能是答案，因此需要 mid 留在区间内- 注意：这里不可能是
left = mid; right = mid-1;，由于mid为向下去中，考虑[0,1]区间，mid = 0，如果此时 nums[mid] < target，mid会一直停留在left。即对于两个数的区间，mid == left，此时如果left不变化，则会陷入无限循环中
# 折线图
二分法的题目尽量画折线图辅助理解。