# 二分法

TIP

二分法又可以被称为二分查找，它描述了在有序集合中搜索特定值的过程。广义的二分查找是将问题的规模尽可能的缩小到原有的一半

对于二分法的思想大家都能讲出几句，但我们仍然很难讲其与实际应用完美的结合到一起，所以我们尽量汇总二分法的应用场景，和大家一起深入，共勉！

# 一、常见问题

给定一个由数字组成的有序数组 nums，并给你一个数字 target。问 nums 中是否存在 target。如果存在，则返回其在 nums 中的索引。如果不存在，则返回 - 1。

这是二分查找中最简单的一种形式。当然二分查找也有很多的变形，这也是二分查找容易出错，难以掌握的原因。

常见变体有：

  • 如果存在多个满足条件的元素，返回最左边满足条件的索引。
  • 如果存在多个满足条件的元素，返回最右边满足条件的索引。
  • 数组不是整体有序的。 比如先升序再降序，或者先降序再升序。
  • 将一维数组变成二维数组...等等

# 二、二分查找中使用的术语

如前所述，二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。但要注意排序的成本

  • target: 要查找的值
  • index: 查找时的当前位置
  • left 和 right: 左右指针
  • mid: 左右指针的中点，用来确定我们应该向左查找还是向右查找的索引

在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

注意：

  1. 二分法搜索可以采用许多替代形式
  2. 可能并不总是直接搜索特定值
  3. 你不一定能直接缩小一半的查找范围
  4. ...

看过之后的几个模版，并结合配套的例题，相信你会有自己的想法。

# 三、模版 I - 基础二分查找

模版 I 是基础的二分查找，用于查找可以通过访问数组中的单个索引来确定的元素或条件。

# 3.1 复杂度分析

  • 平均时间复杂度： O(logN)
  • 最坏时间复杂度： O(logN)
  • 最优时间复杂度： O(1)

# 3.2 关键点

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

# 3.3 区分语法

  1. 初始条件：
  • left = 0
  • right = arrar.length-1 或 number
  1. 终止：left > right
  2. 向左查找：right = mid-1
  3. 向右查找：left = mid+1

# 3.4 javascript 基础模版

var search = function(nums, target) {
  left = 0; // 初始左边界
  right = nums.length - 1; // 初始右边界
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2); //防止溢出
    if (nums[mid] < target) {
      // 收缩左边界
      left = mid + 1;
    } else if (nums[mid] > target) {
      // 收缩右边界
      right = mid - 1;
    } else {
      return mid; // 找到了当前值
    }
  }
  return -1;
};

# 3.5 代码分析

  1. 确定初始的左右边界:
    • left: 0
    • right: nums.length-1
    • mid: (left + (right - left) >> 1)
  2. 如果中间元素值nums[mid] < target：证明中间值左侧包括中间值都不符合要求，可以直接排除，left = mid + 1
  3. 如果中间元素值nums[mid]：证明中间值右侧包括中间值都不符合要求，可以直接排除，right = mid - 1
  4. 如果中间元素值nums[mid] = target：直接返回mid的下标
  5. 重新定义了左右边界，也需要重新计算中间值，我们需要继续进行范围的排除
  6. 定义搜索的条件，应该是搜索区间都不为空，即left <= right

# 3.6 LeetCode 实战

下面五题，难度递增，每篇题解都包含原题链接、模版分析、Js 题解，大家可以放心食用，我们一起加油～

  1. 二分查找（easy）
  2. 搜索插入的位置（easy）
  3. x 的平方根（easy）
  4. 猜数字大小（easy）
  5. 搜索旋转排序数组（middle）

# 四、模版 II - 依赖当前元素与右元素的关系

模板 II 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。

# 4.1 关键点

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

# 4.2 区分语法

  • 初始条件：left = 0, right = length
  • 终止：left == right
  • 向左查找：right = mid 这是因为向右判断，一般需要保留比较元素，否则某些晴情况下会丢失数据
  • 向右查找：left = mid+1

# 4.3 javascript 基础模版

var search = function(nums, target) {
  left = 0; // 初始左边界
  right = nums.length - 1; // 初始右边界
  while (left <= right) {
    var mid = left + Math.floor(left + (right - left) / 2); //防止溢出
    if (target == nums[mid]) {
      right = mid + 1; // 继续寻找左侧是否仍存在满足条件的元素，但包含当前元素
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  if (left != nums.length && nums[left] === target) return left;
  return -1;
};

# 4.4 代码分析

首先定义搜索区间为 [left, right]，注意是左右都闭合，之后会用到这个点。

  1. 终止搜索条件为 left <= right。
  2. 循环体内，我们不断计算 mid ，并将 nums[mid] 与 目标值比对。
  3. 如果 nums[mid] 等于目标值， 则收缩左边界，注意它此时不代表最终结果
  4. 如果 nums[mid] 小于目标值， 说明目标值在 mid 右侧，这个时候搜索区间可缩小为 [mid + 1, right]
  5. 如果 nums[mid] 大于目标值， 说明目标值在 mid 左侧，这个时候搜索区间可缩小为 [left, mid - 1]
  6. 最后我们要判断 left 值是否等于 target，如果不等于，证明没找到
  7. 如果 left 出了右边边界了，说明也没有找到

# 4.5 LeetCode 实战

下面 3 题，难度递增，每篇题解都包含原题链接、模版分析、Js 题解，大家可以放心食用，我们一起加油～

  1. 第一个错误的版本（easy）
  2. 寻找峰值（middle）
  3. 寻找旋转排序数组中的最小值（middle）

# 五、模板 III - 依赖当前元素与左右两个元素之间的关系

模板 III 是二分查找的另一种独特形式。它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。

# 5.1 关键点

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

# 5.2 区分语法

  • 初始条件：left = 0, right = length - 1
  • 终止：left + 1 === right
  • 向左查找：right = mid
  • 向右查找：left = mid

# 5.3 javascript 基础模版

function binarySearch(nums, target) {
  const len = nums.length;
  if (len === 0) return -1;
  let left = 0;
  let right = len - 1;
  while (left + 1 < right) {
    let mid = left + ((right - left) >> 1);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid;
    } else {
      right = mid;
    }
  }
  if (nums[left] == target) return left;
  if (nums[right] == target) return right;
  return -1;
}

# 5.4 代码分析

因为我们的判断区间最少为 2 个元素，所以我们要注意循环的执行条件

  1. 简单的判断边界： nums.length === 0，return -1；
  2. 定义初始的左右边界：left = 0, right = nums.length - 1；
  3. 确定执行条件：left + 1 < right，这也意味着查找区间要存在 3 个元素；
  4. 向左查找时：right = mid；
  5. 向左查找时：left = mid；
  6. 判断剩下的两个元素哪个符合目标元素，并返回结果；

# 5.5 LeetCode 实战

下面 3 题，难度递增，每篇题解都包含原题链接、模版分析、Js 题解，大家可以放心食用，我们一起加油～

  1. 在排序数组中查找元素的第一个和最后一个位置（hard）
  2. 寻找峰值（middle）
  3. 寻找旋转排序数组中的最小值（middle）

# 六、二分查找模板分析

本小结引自于LeetCode二分专题 (opens new window)

上面提到的三个模版，大家在做题的时候很难完全套用进去，大部分时候，都是寻找最合适的方式并不断调整

# 6.1 模版差异

这 3 个模板的不同之处在于：

在这里插入图片描述

  • 左、中、右索引的分配。
  • 循环或递归终止条件。
  • 后处理的必要性。

个人感觉模版I最实用（其实是另外两个模版掉头发啊！）

# 6.2 模版示例

模板I (left <= right)

二分查找的最基础和最基本的形式。

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

模板II (left < right)

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

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

模板III (left + 1 < right)

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

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

# 七、其他经典问题

# 八、写在最后

本文解释了三种最常见的解题模版，并附上LeetCode实战，帮助我们理解二分法这种思想。

如果对你有所帮助不妨给本项目的github 点个 star (opens new window)，这是对我最大的鼓励

关于我

  • 花名：余光
  • WX：j565017805
  • 沉迷 JS，水平有限，虚心学习中

其他沉淀

Last Updated: 8/6/2021, 6:58:15 PM