AI summary
type
status
date
slug
summary
category
tags
icon
password
二分搜索的精髓在于快速收缩搜索区间。本文带大家看一看二分搜索算法在数组中的经典运用场景。

二维数组中的二分搜索

前文讲的二分搜索都是在一维数组中的，在二维矩阵中如何施展二分搜索呢？

566. 重塑矩阵

在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。
给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。
如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
这题不难，但指出了一个必知必会的算法技巧：多维坐标之间的映射转换。
我直接说结论：任何多维数组都可以被映射到一维，所以甭管几维数组，你统一把多维的坐标转化成一维，然后再从一维坐标转化到多维。实际上，多维数组也是一维存储的。
所以这道题，我们先把二维坐标转化成一维，然后再转化成不同 shape 的二维坐标即可。我这里实现了通用的 get/set 函数。
哈哈，这题其实和二分搜索没有关系 (手动狗头)，只是为下一题做铺垫。
Python 内置函数 divmod(a, b) 用于同时计算 商 和 余数，返回一个 包含商和余数的元组 (quotient, remainder)。

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：
  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
用前面的 get 函数把二维数组 matrix 的元素访问抽象成在一维数组中访问元素，然后直接施展最基本的二分搜索即可。

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
作为 74. 搜索二维矩阵 的进阶题目，这道题用不了二分搜索算法。可以用一个小巧思：
我们不要从左上角开始，而是从右上角开始，规定只能向左或向下移动。
你注意，如果向左移动，元素在减小，如果向下移动，元素在增大，这样的话我们就可以根据当前位置的元素和 target 的相对大小来判断应该往哪移动，不断接近从而找到 target 的位置。
当然，如果你想从左下角开始，规定只能向右或向上移动也可以。

二分搜索判定子序列

没想到吧，二分搜索可以用来高效解决子序列的判定问题。

392. 判断子序列

给定字符串 s 和 t，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
这道题很简单，利用双指针即可。如下图：
notion image
但这题的进阶版 792. 匹配子序列的单词数 比较有难度，如果有很多 s，你每次都这样用 for 循环判断子序列，效率就比较低了，需要利用二分搜索技巧来判断子序列。

792. 匹配子序列的单词数

给定字符串 s 和字符串数组 words, 返回  words[i] 中是 s 的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
  • 例如， “ace” 是 “abcde” 的子序列。
现在输入了多个 wrod[i] 让你来判断是否是 s 的子序列，这道题的暴力解法就是像 392. 判断子序列 那样，直接用嵌套 for 循环一个个比较 s 和 word[i] 的字符比较来判断子序列，事件复杂度是平方级别。
这个暴力解法中，对于每个 word[i]，都要重复遍历一遍 s，这是比较傻的，或许我们可以优化一下这个过程？
答案是用二分搜索，先把 s 中的字符预处理一下，把每个字符出现的的索引列表算出来，用空间换时间。如下图所示：
notion image
然后就可以用二分搜索优化了，假如已经匹配了 "ab"，应该匹配 "c" 了。
如果按照暴力解法，我们需要 j 向前线性扫描寻找 s[j] == "c"，但借助这个 index 映射中记录的信息，可以二分搜索 index[c] 中比 j 大的那个索引，在上图的例子中，就是在 [0,2,6] 中搜索大于等于 4 的那个索引。
这样就可以直接得到下一个 "c" 的索引。可以想象，如果字符串 s 非常长的时候，二分搜索可以节约很多线性遍历的时间。
现在的问题就是，如何用二分查找计算那个大于等于 4 的索引呢？答案是，寻找左侧边界的二分搜索就可以做到，具体的原因和代码框架我在 二分搜索算法核心代码模版 写过，这里就不展开了。
注意：这里的 left_bound，允许 target 不存在，所以直接返回 left 即可。

二分搜索+数组双指针

二分搜索结合数组双指针技巧，可以解决「最接近元素」相关的问题。

658. 找到 K 个最接近的元素

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
  • |a - x| < |b - x| 或者
  • |a - x| == |b - x| 且 a < b
我们就说一个最简单直接的方式：用前文中介绍的搜索左侧边界的二分查找算法找到 x 的位置，然后用 双指针技巧秒杀七道数组题目 中解决 5. 最长回文子串 的从中间向两端的双指针算法找到这 k 个元素。
为什么是搜索左侧边界的二分搜索？可以仔细看下前文 二分搜索算法核心代码模版，有提到左侧边界二分搜索的理解。
另外，因为题目要求返回的结果必须按升序排序，所以我们必须用 deque 来从两端添加结果，使得结果有序。
注意：
  • left, right = pos, pos 会重复加入
  • 这里的 left_bound 不能返回 -1，要返回 len(nums)，例子：arr=[3,5,8,10], x=15，k=2，结果应该是 [8,10]

寻找峰值

二分搜索的精髓在于快速收缩搜索区间，寻找数组中的「峰值」是经典的二分搜索考题，请仔细体会本题是如何快速收缩搜索区间的。

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
当目标元素 target 不存在数组 nums 中时，搜索左侧边界的二分搜索的返回值可以做以下几种解读：
  1. 返回的这个值是 nums 中大于等于 target 的最小元素索引。
  1. 返回的这个值是 target 应该插入在 nums 中的索引位置。
  1. 返回的这个值是 nums 中小于 target 的元素个数。
比如在有序数组 nums = [2,3,5,7] 中搜索 target = 4，搜索左边界的二分算法会返回 2，你带入上面的说法，都是对的。
所以以上三种解读都是等价的，可以根据具体题目场景灵活运用，显然这里我们需要的是第二种。
代码直接搬上面的 left_bound 即可，略。

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
提示：
  • 1 <= nums.length <= 1000
  • 2^31 <= nums[i] <= 2^31 - 1
  • 对于所有有效的 i 都有 nums[i] != nums[i + 1]
本题让你求「峰值」元素索引，要是线性遍历的话没什么难度，所以题目要求你必须用二分搜索算法来做。
一般的二分搜索题目要根据 left, right 和 mid 的大小关系来判断到底应该搜索左侧还是右侧边界，而这道题如果考察 left, right 和 mid 之间的相对大小会比较麻烦，你可能需要分很多种情况讨论，比如 nums[mid] < nums[left] < nums[right]、nums[mid] > nums[left] > nums[right] 等等，写起来比较繁琐。
这道题更好的思路是不要考虑 left 和 right，单纯考虑 mid 周边的情况。具体来说，我们计算 nums[mid] 和 nums[mid+1] 这两个元素的相对大小，即可得到 mid 附近的元素走势：
如果走势下行（nums[mid] > nums[mid+1]），说明 mid 本身就是峰值或其左侧有一个峰值，所以需要收缩右边界（right = mid）；
如果走势上行（nums[mid] < nums[mid+1]），则说明 mid 右侧有一个峰值，需要收缩左边界（left = mid + 1）。
因为题目说了 nums 中不存在相等的相邻元素，所以不用考虑 nums[mid] == nums[mid+1] 的情况，依据以上分析即可写出代码。
有人要问了：不是说二分搜索用于单调函数吗？这 nums 也不单调啊。
答：因为这里题目只要求返回 任何一个峰值 所在位置即可。
注意 mid+1 防越界。

852. 山脉数组的峰顶索引

给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
直接把 162 题的解法复制过来即可通过。略。

LCR 172. 统计目标成绩的出现次数

某班级考试成绩按非严格递增顺序记录于整数数组 scores，请返回目标成绩 target 的出现次数。
和 34. 在排序数组中查找元素的第一个和最后一个位置 有些类似，用二分搜索找到左右边界的索引，就可以判断重复出现的次数了。略。

LCR 173. 点名

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
常规的二分搜索让你在 nums 中搜索目标值 target，但这道题没有给你一个显式的 target，怎么办呢？
其实，二分搜索的关键在于，你是否能够找到一些规律，能够在搜索区间中一次排除掉一半。比如让你在 nums 中搜索 target，你可以通过判断 nums[mid] 和 target 的大小关系判断 target 在左边还是右边，一次排除半个数组。
所以这道题的关键是，你是否能够找到一些规律，能够判断缺失的元素在哪一边？
其实是有规律的，你可以观察 nums[mid] 和 mid 的关系，如果 nums[mid] 和 mid 相等，则缺失的元素在右半边，如果 nums[mid] 和 mid 不相等，则缺失的元素在左半边。
然后用左侧边界的二分搜索定位缺失的元素位置。对应其功能 2.返回的这个值是 target 应该插入在 nums 中的索引位置。

特殊数组上的二分搜索

二分搜索算法不仅能应用在排好序的数组，如果这个数组不是一个标准的有序数组，只要稍微修改算法逻辑，也能使用二分搜索。还是那句话，二分思想的核心在于快速收缩搜索区间。

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
这是一道经典的二分搜索题目，只要把图画出来，难度不算大。
把一个排好序的数组就好比一段斜向上的山坡，沿着一个元素旋转数组，相当于将山坡切断并旋转，在原本平滑的山坡上产生一个「断崖」：
notion image
注意「断崖」左侧的所有元素比右侧所有元素都大，我们是可以在这样一个存在断崖的山坡上用二分搜索算法搜索元素的，主要分成两步：
  1. 确定 mid 中点落在「断崖」左侧还是右侧。
  1. 在第 1 步确定的结果之上，根据 target 和 nums[left], nums[right], nums[mid] 的相对大小收缩搜索区间。
具体来说，看图很容易得到：如果 nums[mid]≥nums[left]，那么 mid 就在左边，否则在右边。

81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
你必须尽可能减少整个操作步骤。
本题和 33 题很类似，不过本题的关键在于题目说数组中可能存在重复元素。
而对于这道题，nums 中存在重复元素，会影响到第 1 步，你比如说输入旋转后的数组 nums = [2,2,2,2,0,1,2]，画成图就是这样：
notion image
如上图，mid 将会落到左侧的直线上，此时 nums[left] == nums[mid] == nums[right]，无法根据它们的相对大小判断「断崖」到底在 mid 的左边还是右边，从而无法进入第 2 步。
我们的解决方案就是：不要出现 nums[left] == nums[mid] == nums[right] 的情况，即在计算 mid 之前收缩 left, right 边界，提前消除重复元素：
notion image
这样 mid 必然出现在山坡上，不会和 nums[left], nums[right] 相等，然后就可以正常执行第 2 步逻辑，和第 33 题的解法完全相同了，具体看解法代码。