二分查找一般由三个主要部分组成:

  1. 预处理 —— 如果集合未排序,则进行排序。
  2. 二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
  3. 后处理 —— 在剩余空间中确定可行的候选者。

    模板

    image.png
    这 3 个模板的不同之处在于:
  • 左、中、右索引的分配。
  • 循环或递归终止条件。
  • 后处理的必要性。

模板 #1 和 #3 是最常用的,几乎所有二分查找问题都可以用其中之一轻松实现。模板 #2 更 高级一些,用于解决某些类型的问题。

模板 #1(left <= right)

  • 二分查找的最基础和最基本的形式。
  • 查找条件可以在不与元素的两侧进行比较的情况下确定(或使用它周围的特定元素)。
  • 不需要后处理,因为每一步中,你都在检查是否找到了元素。如果到达末尾,则知道未找到该元素。

    模板 #2(left < right):

  • 一种实现二分查找的高级方法。

  • 查找条件 需要访问元素的直接右邻居
  • 使用元素的右邻居来确定是否满足条件,并决定是向左还是向右。
  • 保证查找空间在每一步中至少有 2 个元素。
  • 需要进行后处理。 当你剩下 1 个元素时,循环/递归结束。 需要评估剩余元素是否符合条件。

    模板 #3(left + 1 < right):

  • 实现二分查找的另一种方法。

  • 搜索条件 需要访问元素的直接左右邻居
  • 使用元素的邻居来确定它是向右还是向左。
  • 保证查找空间在每个步骤中至少有 3 个元素。
  • 需要进行后处理。 当剩下 2 个元素时,循环/递归结束。 需要评估其余元素是否符合条件。