数据结构专题（一）二分法，寻找解题思路看这一篇就够了

程序员文章站 2022-06-26 16:34:19

和大家一起掌握二分法，本篇文章提供了三个模版，以及大量配套练习题，帮助大家清晰的认识二分法，逐渐了解、掌握相关问题。...

二分法

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

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

一、常见问题

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

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

常见变体有：

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

数据结构专题（一）二分法，寻找解题思路看这一篇就够了

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

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

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

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

注意：

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

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

数据结构专题（一）二分法，寻找解题思路看这一篇就够了

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

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

3.1 复杂度分析

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

3.2 关键点

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

3.3 区分语法

初始条件：

left = 0
right = arrar.length-1 或 number

终止：left > right
向左查找：right = mid-1
向右查找：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 代码分析

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

3.6 LeetCode 实战

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

数据结构专题（一）二分法，寻找解题思路看这一篇就够了

四、模版 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]，注意是左右都闭合，之后会用到这个点。

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

4.5 LeetCode 实战

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

数据结构专题（一）二分法，寻找解题思路看这一篇就够了

五、模板 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;
}