二分查找-总结
9/9/2022 二分查找
# 模板总结
模板代码的不同点如下图红色部分所示：
这 3 个模板的不同之处在于：
- 左、中、右索引的分配。
- 循环或递归终止条件。
- 后处理的必要性。
其中模板一为基础二分法；模板二更为强大，能够解决查找符合某个条件下的值；模板三感觉作用不大。
# 模板 #1 (left <= right)
- 二分查找的最基础和最基本的形式。
- 查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
- 不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。
# 模板 #2 (left < right)
- 一种实现二分查找的高级方法。
- 查找条件需要访问元素的直接右邻居。
- 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
- 保证查找空间在每一步中至少有 2 个元素。
- 需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。
# 模板 #3 (left + 1 < right)
- 实现二分查找的另一种方法。
- 搜索条件需要访问元素的直接左右邻居。
- 使用元素的邻居来确定它是向右还是向左。
- 保证查找空间在每个步骤中至少有 3 个元素。
- 需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。
# 时间复杂度和空间复杂度
- 时间复杂度：O(lgn)，对数级别
- 空间复杂度：O(1)，常量空间