总结

难点

• while的时候的终止条件是 l < r 还是 l <=
• 更新左右边界的时候，该怎么更新
• 初始化左右边界的时候，应该选择excludsive还是inclusive的边界。

• 如何实现最左/右值搜索

  解决方法

  针对以上难点，我通过总结前任的经验摸索了一套思维框架

• 解空间就是答案可能存在的区间，根据情况判断是当剩下一个元（while (l < r)）素时结束循环。目前为止，154题必须需要在解空间剩下一个元素的时候结束。

• 更新左右边界就是去掉那一部分一定不是答案的区域

  // 搜索最左边第一个大于等于X的，X最左插入位置
  while (l < r){
    int m = l + (r - l) / 2;
    if (nums[m] >= X){
        // impossible range [m+1, r]
        r = m;
    }else if (nums[m] < X){
        // impossible range [l, m]
        l = m+1;
    }
  }
  // l == r, 解空间里面剩余的唯一解
  return l;

  // 搜索最右边边第一个大于X的，X的最右插入位置
  while (l < r){
    int m = l + (r - l) / 2;
    if (nums[m] > X){
        // impossible range [m + 1, r]
        r = m;
    }else if (nums[m] <= X){
        // impossible range [l, m]
        l = m+1;
    }
  }
  // l == r, 解空间里面剩余的唯一解
  return l;
  

概念

https://segmentfault.com/a/1190000039377221

解空间

• 包含答案的集合，这个集合只能偏大不能偏小，偏小会错过答案。
• 但是可以合理的缩小解空间来提升效率（高级技巧）。

有序序列

• 题中明显给出
• 需要自己推理的，比如数组内全为非负，这样子前缀和 或者 前缀异或 就是递增序列了

极值

• 一般是求满足某个条件的第K大/小的解

一个中心（难点）

• 二分法就是要将解空间折半，确认哪一半一定不是解
• 难点在于 根据什么条件 来 舍弃哪一部分

题型

基础二分法

1337. 矩阵中战斗力最弱的 K 行

69. x 的平方根 (Done)

• 记得用除法解决溢出问题

  367. 有效的完全平方数 (Done)

• 记得用除法解决溢出问题以及乘以1.0来做float除法

  29. 两数相除 不能使用*, /, %(Done)

• 如何处理结果溢出，以前没做过

• 如何处理负数除法，这个特别不好做
• 总结：这个把正负数统一成正数除法来处理，因为负数商和正数商都是取整数部分。最后，判断一下符合即可。

• 坑：Math.abs(Integer.MIN_VALUE) == Integer.MIN_VALUE; 这玩意的相反数等于他自己。。。，以后做相反数，别用Math.abs()

  山峰数组**

  162. 寻找峰值 **(多练)

• 这题也太难想到二分了，题目给的最后一句话是二分法合法性的关键。

• 其实峰值是三种情况，全增，全减，先增后减。

答案：

• 由于题目确保任意两个连续的数组不想等，所以数组要么全部递增，要么全部递减，要么中间起起伏伏，所以一定存在峰值节点
• 二分法
  • 我们比较nums[m]和nums[m+1]
  • 首先如果m = nums.length - 1，那么他就是最后一个节点，此时搜索区间也就他这一个可能答案了（不然(r+l)/2不可能等于nums.length - 1），所以他就是答案了，返回m。
  • 接着我们看nums[m] 和nums[m+1]的比较结果
    • nums[m] < nums[m+1]
      • 表明m可能是答案，m处在下降部分。
        • 如果m-1对应的元素小于m对应的元素那么m就是答案。反之则不是，但是可以确定的是：
          • 如果m不是答案，答案一定在左边。
          • 如果m是答案，且左边不存在答案，最后左边区间会被压缩为0，最后l会指向现在的m。所以r=m-1一定会找到答案。
      • 缩短答案区间至r = m - 1
    • nums[m] > nums[m+1]
      • 表明m不可能是答案，因为他的右边元素比他大
      • 缩短答案区间至l = m + 1

复习

• 第一次复习，不太熟练了。没做出来，没理解透。自己理解了一下，还是有些模糊，就加强记忆吧。

852. 山脉数组的峰顶索引 (多练)

• 第一次复习，pass，熟练

  最左位置插入

  如果存在多个满足条件的元素，返回最左边满足条件的索引。

  // 搜索最左边第一个大于等于X的，X最左插入位置
  while (l < r){
    int m = l + (r - l) / 2;
    if (nums[m] >= X){
        // impossible range [m+1, r]
        r = m;
    }else if (nums[m] < X){
        // impossible range [l, m]
        l = m+1;
    }
  }
  // l == r, 解空间里面剩余的唯一解
  return l;
  

最右位置插入

如果存在多个满足条件的元素，返回最右边满足条件的索引。

// 搜索最右边边第一个大于X的，X的最右插入位置
while (l < r){
    int m = l + (r - l) / 2;
    if (nums[m] > X){
        // impossible range [m + 1, r]
        r = m;
    }else if (nums[m] <= X){
        // impossible range [l, m]
        l = m+1;
    }
}
// l == r, 解空间里面剩余的唯一解
return l;

剑指 Offer 53 - II. 0～n-1中缺失的数字 (Done)

区间查找**

剑指 Offer 53 - I. 在排序数组中查找数字 I (Done)

• 先查最左边的大于等于x的元素，如果index==length或者nums[index] != x，则说明该数组不包含x，返回0

• 接着查最左边第一个大于x的元素，之后rihgt-left就是答案了

  34. 在排序数组中查找元素的第一个和最后一个位置（多练）

  反转数组**

  153. 寻找旋转排序数组(unique)中的最小值（多练）

• 确定m是在左边还是右边有序数组，然后判断target可不可能在这一区间，然后更新index

  154. 寻找旋转排序数组中的最小值 II（Done）

• 这题好难做，重复的元素出现之后，好难确定条件。

• 没有掌握，还是看m是在那一块排好序的segment。注意的是，当m同时等于左边界和右边界的时候，我们无法判断m在哪里，但是可以排出左边界和右边界为答案，所以l++ l—

  33. 搜索旋转排序数组(Done)

• 找最大值的索引，然后+1就是最小值。注意，记得+1后mod数组长度，如果最大值为最右元素，最小值在index为0的地方。

  81. 搜索旋转排序数组 II(Done)

• 这和154完全不一样，好难啊。

• 看不懂，答案理解不了。无法用自己的二分方式做出来。
• 把他的答案背下来吧，智商不够，就靠背吧。
• 答案
  • 解空间：[0, length-1]
  • 二分搜索目标：最小值的index
  • 终止条件：当解空间的大小为一的时候，该解为最小值的index. while (l < r)
  • 循环内：

    - 若nums[m] == nums[r], 则可以排除r肯定不是答案，r--
    - 若nums[m] > nums[r]，则可以确定[l, m]都不是最小值，l = m + 1
    - 若nums[m] < nums[r]，则可以确定 (m, r]都不是最小值，r = m;
    

  • 循环结束，因为l==r，所以他们都代表了最小值的索引。
  • 返回, nums[l];

    能力检测二分**

    能力检测二分一般是：定义函数 possible， 参数是 mid，返回值是布尔值。外层根据返回值调整”解空间”。能力检测二分只是将 while 内部的 if 语句调整为了一个函数罢了。
    示例代码（以最左二分为例）：

    def ability_test_bs(nums):
    def possible(mid):
    pass
    l, r = 0, len(A) - 1
    while l <= r:
     mid = (l + r) // 2
     # 只有这里和最左二分不一样
     if possible(mid): l = mid + 1
     else: r = mid - 1
    return l
    

    LCP 12. 小张刷题计划 （Undo）

1011. 在 D 天内送达包裹的能力（Done）

答案：

• 写出一个possible函数，返回是否可以在小于等于days之内以capacity的运载量完成运输
• 解空间：[最大包裹重量，包裹重量总和]
• 二分搜素目标：capacity的最小值
• 终止条件：解空间为空，答案会保留在r+1的地方，也就是最少的capacity
• 循环内
  • 如果possible的话，我们保留这个capacity为candidate，然后去搜索[l, m-1]区间内是否还有更短的时间
  • 如果not possible的话，我们去搜索[m+1, r]这个更大的区间
• 循环结束：答案在r+1的位置，也就是l的位置

• 返回：l

  875. 爱吃香蕉的珂珂 (Done)

  判断吃m个h能不能吃完

• 能吃完，把m变小，r = m - 1，去检查更小的值

• 吃不完，把m变大，l = m + 1，去检查更大的值

  475. 供暖器 （Done）

  先排序+二分查找
  这个还是比较难的，possible函数需要基于排序

778. 水位上升的泳池中游泳 (Undo)

1482. 制作 m 束花所需的最少天数(Done)

答案

• 写出一个possible函数，返回day天之后，是否可以制作至少m束花。
• 解空间：[1, max(bloomDay)]
• 二分搜索目标: 制作m束花最少需要几天
• 终止条件：解空间为空则停止，答案会保留在r+1的地方，也就是最少可以满足的天数
• 循环内
  • 如果possible的话，我们保留这个day为candidate，然后去搜索[l, m-1]区间内是否还有更短的时间
  • 如果not possible的话，我们去搜索[m+1, r]这个更大的区间
• 循环结束：答案在r+1的位置，也就是l的位置
• 返回：l

  计数二分

  找出第k小/大的某个东西（元素或者值）

  def count_bs(nums, k):
  def count_not_greater(mid):
    pass
  l, r = 0, len(A) - 1
  while l <= r:
      mid = (l + r) // 2
      # 只有这里和最左二分不一样
      if count_not_greater(mid) > k: r = mid - 1
      else: l = mid + 1
  return l
  

719. 找出第 k 小的距离对(Done)

先排序，然后计数，是否有大于或等于k个数小于等于distance

• 若是，则distance是可能答案，缩小distance，r=distance-1
• 若不是，则扩大distance，l=distance+1

难点在于count函数，要算有多少个pair小于等于distance，因为我们找的是最左的元素。

前缀和二分

前面说了：如果数组全是正的，那么其前缀和就是一个严格递增的数组，基于这个特性，我们可以在其之上做二分。类似的有单调栈/队列。这种题目类型很多，为了节省篇幅就不举例说明了。提出前缀和二分的核心的点在于让大家保持对有序序列的敏感度。

209. 长度最小的子数组（Done）

• 滑窗（O（n）） 或者 二分法（O（nlogn））

• 这题要搜最右边的使得条件成立的解，所以记得+1，candidate是放在了左边的后一个，l-1的地方。

  528. 按权重随机选择 （Done）

• Random rand = new Random()

• rand.nextInt(x); [0, x)
• 这题要搜第一个大于前缀的元素，所以当当前前缀小于等于x，我们往大了找，l = m + 1，反之，r = m - 1；

  插入排序二分

  太难了，暂时放弃了

Appendix

第一次复习

2021-07-11

山脉数组

162. 寻找峰值

• 忘了

  852. 山脉数组的峰顶索引

• 熟练

  区间查询

  34. 在排序数组中查找元素的第一个和最后一个位置

• 稍有遗忘

  • 如何判断这个数组中是否包含target元素
  • 记得check全部没找到的情况，l == nums.length + 直接access元素对比就行了

    旋转数组

    33. 搜索旋转排序数组

    完全不记得了，自己摸索了一下，是在正确的路上了，当时理解的不够透彻
    有两个判断条件

• 左边还是右边是一定有序的

• 判断target应该在那一部分+判断nums[m]和target的大小比较，从而来更新左右边界

81. 搜索旋转排序数组 II

多练，面试遇到就没了。
重复的问题解决了一半，记得在变化左右边界的时候，考虑target等于边界元素的情况！！！

153. 寻找旋转排序数组中的最小值

不会了。
这题只能和原数组的端点比较，不能和 nums[r]比较。
记得处理全部是增长的情况，就是说返回nums[l % length]2

154. 寻找旋转排序数组中的最小值 II

这题是个特例，停止条件是 while (l < r) 搜索空间只剩一个时就是答案。

能力检测二分

875. 爱吃香蕉的珂珂

熟练通过

LCP 12. 小张刷题计划

possible函数没写出来

计数二分

274. H 指数

熟练通过

前缀和二分

209. 长度最小的子数组

做出来了

总结

• 第一次复习，二分法的基本思想和框架并没有遗忘，但是对于特殊的题型，旋转数组，山峰数组，基本上做不出来了，问题比较大的就是这么五道题。

——————
以下为最开始做笔记的草稿。

题型

https://leetcode-cn.com/circle/discuss/3tYCu3/
其中两种类型主要解决的的是：这道题我的解空间以及明确出来了，如何用代码找出具体的值（如何选择去掉哪一半）。而四大应用主要解决的是：如何构造解空间（更多的情况则是如何构建有序序列）以及一些变体。

两种类型

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

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

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

寻找满足条件的值

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

思维框架

• 首先定义解空间为 [left, right]，注意是左右都闭合
• 由于定义的解空间为 [left, right]，因此当 left <= right 的时候，解空间都不为空，此时我们都需要继续搜索。 也就是说终止搜索条件应该为 left <= right。
• 循环体内，我们不断计算 mid ，并将 nums[mid] 与 目标值比对。
  • 如果 nums[mid] 等于目标值， 则提前返回 mid（只需要找到一个满足条件的即可）
  • 如果 nums[mid] 小于目标值， 说明目标值在 mid 右侧，这个时候解空间可缩小为 [mid + 1, right] （mid 以及 mid 左侧的数字被我们排除在外）
  • 如果 nums[mid] 大于目标值， 说明目标值在 mid 左侧，这个时候解空间可缩小为 [left, mid - 1] （mid 以及 mid 右侧的数字被我们排除在外）

• 循环结束都没有找到，则说明找不到，返回 -1 表示未找到。

  public int binarySearch(int[] nums, int target) {
    // 左右都闭合的区间 [l, r]
    int left = 0;
    int right = nums.length - 1;
  
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid;
        if (nums[mid] < target)
                  // 解空间变为 [mid+1, right]
            left = mid + 1;
        if (nums[mid] > target)
            // 解空间变为 [left, mid - 1]
            right = mid - 1;
    }
    return -1;
  }
  

  寻找最左插入位置(最左二分)

  上面我们讲了寻找满足条件的值。如果找不到，就返回 -1。那如果不是返回 -1，而是返回应该插入的位置，使得插入之后列表仍然有序呢？
  比如一个数组 nums: [1,3,4]，target 是 2。我们应该将其插入（注意不是真的插入）的位置是索引 1 的位置，即 [1,2,3,4]。因此寻找最左插入位置应该返回 1，而寻找满足条件的位置 应该返回-1。
  另外如果有多个满足条件的值，我们返回最左侧的。 比如一个数组 nums: [1,2,2,2,3,4]，target 是 2，我们应该插入的位置是 1。

思维框架

• 首先定义解空间为 [left, right]，注意是左右都闭合
• 由于定义的解空间为 [left, right]，因此当 left <= right 的时候，解空间都不为空，此时我们都需要继续搜索。 也就是说终止搜索条件应该为 left <= right。
• 循环体内，我们不断计算 mid ，并将 nums[mid] 与 x 比对。
  • 当 A[mid] >= x，说明找到一个备胎（candidate answer），我们令 r = mid - 1 （也就是说r+1就是目前最好的candidate answer）将 mid 从解空间排除，继续看看有没有更好的备胎。
  • 当 A[mid] < x，说明 mid 根本就不是答案，直接更新 l = mid + 1，从而将 mid 从解空间排除。

• 循环结束, 最后解空间的 l 就是最好的备胎（当循环结束，l总是等于r+1的，所以返回l就等于返回了r+1，就返回了最后一个满足条件的答案），备胎转正。

  def bisect_left(nums, x):
    # 内置 api
    bisect.bisect_left(nums, x)
    # 手写
    l, r = 0, len(A) - 1
    while l <= r:
        mid = (l + r) // 2
        if A[mid] >= x: r = mid - 1
        else: l = mid + 1
    return l
  

  疑问：

• [x] 算法明明是一直压缩右边界，但为什么最后结果是左边界了呢？是不是说结束的时候，左边界代表了最后一个有效的右边界呢？而且在最右插入里面，也是返回l，为什么l就是答案呢？

  • 是这样子的，这个二分算法呢，是消除掉一半区间，然后答案是被隐性的保留在了每一个解空间的r+1的地方。然后呢，当循环结束，l总是等于r+1的，所以返回l就等于返回了r+1，就返回了最后一个满足条件的答案。

    寻找最右插入位置（最右二分）

    思维框架

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

• 由于我们定义的解空间为 [left, right]，因此当 left <= right 的时候，解空间都不为空。 也就是说我们的终止搜索条件为 left <= right。
• 在循环内：
  • 当 A[mid] > x，说明找到一个备胎（candidate answer），我们令 r = mid - 1（也就是说r+1就是最好的candidate answer） 将 mid 从解空间排除，继续看看有没有更好的备胎。
  • 当 A[mid] <= x，说明 mid 根本就不是答案，直接更新 l = mid + 1，从而将 mid 从解空间排除。
• 循环结束后，最后解空间的 l 就是最好的备胎（当循环结束，l总是等于r+1的，所以返回l就等于返回了r+1，就返回了最后一个满足条件的答案），备胎转正。

  def bisect_right(nums, x):
    # 内置 api
    bisect.bisect_right(nums, x)
    # 手写
    l, r = 0, len(A) - 1
    while l <= r:
        mid = (l + r) // 2
        if A[mid] <= x: l = mid + 1
        else: r = mid - 1
    return l
  

  小贴士

  以上就是两种二分的基本形式了。而在实际的写代码过程中，我不会使用寻找满足条件的值模板，而是直接使用最左 或者 最右 插入模板。为什么呢？因为后者包含了前者，并还有前者实现不了的功能。比如我要实现寻找满足条件的值，就可直接使用最左插入模板找到插入索引 i，只不过最后判断一下 nums[i] 是否等于 target 即可，如果不等于则返回 -1，否则返回 i。这也是为什么我将二分分为两种类型，而不是三种甚至四种的原因。