二分查找一般由三个主要部分组成:
- 左、中、右索引的分配。
- 循环或递归终止条件。
- 后处理的必要性。
模板 #1 和 #3 是最常用的,几乎所有二分查找问题都可以用其中之一轻松实现。模板 #2 更 高级一些,用于解决某些类型的问题。
模板 #1(left <= right)
- 二分查找的最基础和最基本的形式。
- 查找条件可以在不与元素的两侧进行比较的情况下确定(或使用它周围的特定元素)。
不需要后处理,因为每一步中,你都在检查是否找到了元素。如果到达末尾,则知道未找到该元素。
模板 #2(left < right):
一种实现二分查找的高级方法。
- 查找条件 需要访问元素的直接右邻居。
- 使用元素的右邻居来确定是否满足条件,并决定是向左还是向右。
- 保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。 当你剩下 1 个元素时,循环/递归结束。 需要评估剩余元素是否符合条件。
模板 #3(left + 1 < right):
实现二分查找的另一种方法。
- 搜索条件 需要访问元素的直接左右邻居。
- 使用元素的邻居来确定它是向右还是向左。
- 保证查找空间在每个步骤中至少有 3 个元素。
- 需要进行后处理。 当剩下 2 个元素时,循环/递归结束。 需要评估其余元素是否符合条件。