Leetcode | 第4节：二分查找，归并排序

大家好！

上一节我们说完了链表的一些高频题。那么这一节，我们会介绍一些二分查找和排序相关的题目。二分和排序本身不是很困难，但是还是有一些难题需要一些技巧才能解决（倒也不是完全毫无头绪的那种），所以这一篇文章，我们除了基本内容外，也会花一些时间介绍一下技巧性的内容。

那么我们开始吧。

算法2：查找算法，二分

二分查找（binary search）是一种查找算法，当然也是最高频的考察点，所以这一节我们绝大部分时间，都会花在二分查找上。

简单介绍一下二分查找的算法。二分查找是在一个有序数组上进行搜索（不妨这里设置为升序），设立一个要查找的元素target，再设立两个指针left, right，分别指向数组的第一个和最后一个元素。然后每一次设定一个mid位置，表示中间值，并且mid = (left + right) / 2。然后每一次比较mid位置的元素和target的大小关系。如果mid位置的元素比target小，那么说明mid太靠前了，应该往后稍稍，因此下一次应该left = mid + 1，相当于下次查找，左半部分就不考虑了，只考虑右半部分。这也是“二分”的含义。反过来的话，那就是right = mid - 1。

那么一直迭代下去，找到了这个元素，就可以返回（当然如果元素有重复，这个时候题目可能会有其他规定，比方说返回最右边的元素）。但是如果我们最终的left > right，就说明并没有查到这个元素，这个时候就说明查找失败了。

当然了，这只是一种二分的实现方式。最后如何实现其实每一个人的写法都有可能略有不同，因此大家掌握了一种写法，然后一直使用这个模板，会比较好一些。

我们再用一张图来描述一下这个过程。

好的，接下来我们来看看具体的题目吧。

Problem 1: Leetcode 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 。

比方说对于数组[4,5,6,7,0,1,2]，如果我们的target = 0，那么返回的就是4，因为位于第4个位置（注意，下标从0开始）。

对于这个问题，如果我们要使用二分，所以肯定会有left, right和mid这三个位置。但注意，我们必须要找到有序的关键信息。

在这里，有几个点要注意。其一是，无论如何旋转，在mid前的一段和mid后的一段，至少会有一段是有序的（这个画画图就能看出来）。其二是，旋转之后，后面一段的最大值，一定小于前面一段的最小值，所以可以通过比较nums[0]和nums[mid]，就能直接发现到底是哪一段有序。其三，找到有序的部分数组之后，我们事实上只需要根据有序数组的最小值和最大值（对应第一个和最后一个元素），就可以判断target是否在这个有序数组内。在的话，就保留这一部分（相当于right = mid - 1），否则的话，就保留另外一部分（相当于left = mid + 1）。

所以可以看出来，其实不完全是严格的二分查找，因为我们并没有直接比较mid和target的关系。但是二分的核心当然也不是这一个比较，而是“寻找有序”和“每次消去一半”的思路。

好的，思路明晰了，代码也就清楚了。

int n = (int)nums.size();
if (!n) {
    return -1;
}
if (n == 1) {
    return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
    int mid = (l + r) / 2;
    if (nums[mid] == target) return mid;
    if (nums[0] <= nums[mid]) {
        if (nums[0] <= target && target < nums[mid]) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    } else {
        if (nums[mid] < target && target <= nums[n - 1]) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
}
return -1;

对于这个题，虽然隐藏的解题要素比较多，但是抓住两个二分题目的关键因素（寻找有序，每次消去一半），其实是非常直接和容易想到的。

这一道题还有一个变种（Leetcode 81），这个题的关键差别在于，数组中的元素可以重复（其余条件不变）。那么这个时候，之前的判断标准就不一定准确（有可能出现nums[left] == nums[mid] == nums[right]的极端情况）。在这个情况下，官方题解也没有特别好的主意，只有最左边和最右边的指针分别向内移动一格，再按照Problem 1的思路去做。具体可以参考原链接，这里就不多说了。

Problem 2: Leetcode 153 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

这一个题目同样是旋转数组，但是区别在于这一次要寻找的是最小元素。怎么寻找这个最小元素呢？

回想二分的主要思路，一是找到有序的部分，二是想办法去消一半。这里的背景和Problem 1相同，所以第一想到的确实是怎么找到有序的部分。但这里有个问题就是，找到有序的部分并不代表最小值在这里，并且你无法直接判断出来最小值是否在这个有序的区间内。所以只能想有没有什么办法，找到一个规则，然后每一次可以消去一半元素。

就像正常的二分查找一样，我们面对的数组，前面一半都比nums[mid]要小，后面一半都比nums[mid]要大。所以事实上，这里如果我们也能够找到一个指标，使得最小值所在位置的前面一半和后面一半有明显的差异，那么自然的，就可以设计规则，来判断我们当前mid所在的位置，究竟是靠左了，还是靠右了。那就自然也可以使用二分的方法了。

这里的一个关键指标是数组的最后一个元素。因为对于数组的最后一个元素而言，最小值前面的一半都会比它大，最小值后面的一半都会比它小。具体可以看下面这张图

可以看出，最小值右边的元素，都小于最右边的元素（除了最右边的元素本身）。而最小值左边的元素，都大于最右边的元素。

在这个结论成立的情况下，mid只需要它与high所在位置的值做一个比较，就可以判断究竟是靠右边，还是靠左边了。具体来说，就是

1. 如果nums[mid] < nums[high]，说明靠右了，那么就应该忽略右半部分，即right = mid - 1。
2. 如果nums[mid] > nums[high]，说明靠左了，那么就应该忽略左半部分，即left = mid + 1。

所以判断规则找到，二分代码也就不难写了。

int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            }
            else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }

再次强调一遍，每一个人写出来的二分查找可能会有细微的区别（比方说代码里的和分析的就有些许不同），但是只要结果正确，问题就不大。

这一个题有一个拓展就是Leetcode 154，同样也是将数组的元素规定为了“可重复”。在这种情况下，有一个可能性是nums[mid] == nums[high]，这个时候只需要让high -= 1就可以了。另外要注意的是，对于Problem 2而言，实际上是不会出现上面说的这种条件的情况的，读者可以自己想一下为什么。

Problem 3: Leetcode 162 峰值元素是指其值大于左右相邻值的元素。 给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

这一个问题就很简单了，只要分析出峰值的特性，然后找到什么情况下，可以消去一半的元素就可以了。可以拿来当作练习。

对于峰值来说，它的左边元素和右边元素都应该比它要小，所以我们要观察的是左右两边元素值的趋势。如果现在mid所在的位置，它比mid + 1位置的元素要小，说明当前趋势是“上升的”，就说明这个峰值应该在右边。所以删去左半部分元素就可以了。另外一个可能性是类似的，这里不多写了。

好的，我们放出核心代码。

int search(int[] nums, int l, int r) {
  if (l == r)
    return l;
  int mid = (l + r) / 2;
  if (nums[mid] > nums[mid + 1])
    return search(nums, l, mid);
  return search(nums, mid + 1, r);
}

最后返回search(nums, 0, nums.length - 1)就可以了。

Problem 4: Leetcode 1011 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

比方说如果weights = [1,2,3,4,5,6,7,8,9,10], D = 5，那么最低的载重是15，在这个情况下，按照顺序切割，1-5天的安排分别是[1, 2, 3, 4, 5], [6, 7], [8], [9], [10]。注意，根据题目要求，不能够调换顺序。

这一个题目二分完全就是一种思想，和数组本身的性质毫无关系，属于另外一种考察二分思想的题。注意观察，如果载重量无穷大（当然实际编程中没必要，把所有货物的重量求个和，就是所必要的最大载重量，再大也没意义），那么一下子把所有货物放上去，一天就能运送完。反过来，如果载重量特别小（但是不能太小，要至少可以装上一件货物），那么每天就只能装上一件。所以我们找到了下限和上限，就直接二分找到最合适的值就可以了。这个合适的意思就是，必须要刚刚好在

天内运送完，并且载重量要最小。

我们先放出代码，再点一个细节。

int left = *max_element(weights.begin(), weights.end()), right = accumulate(weights.begin(), weights.end(), 0);
while (left < right) {
  int mid = (left + right) / 2;
  // need 为需要运送的天数
  // cur 为当前这一天已经运送的包裹重量之和
  int need = 1, cur = 0;
  for (int weight: weights) {
    if (cur + weight > mid) {
      ++need;
      cur = 0;
    }
    cur += weight;
  }
  if (need <= days) {
    right = mid;
  }
  else {
    left = mid + 1;
  }
}
return left;

在这里我们可以看出，我们每选择一个可能的载重量mid，我们就计算，但是注意，判断条件是need <= days而不是need < days，也就是说，为了找到最小的情况，我们即使发现在

天内可以完成，我们也要缩短右边的长度，相当于一直把mid“往左逼”。这样的话，最后找到的值，就是最小的，满足

天要求的载重量。

这一个思想其实也会经常被拿来用来设计寻找非单调递增/单调递减数组的二分查找算法（对比来看，之前的有序数组要求元素是无重复的），本身这个算法也是一个高频考察点（对应Leetcode 34）。在这个时候，常规的二分算法虽然也可以找到target，但是如果要求找到最左边/最右边的target（毕竟有重复嘛），就需要利用到这里提到的思想，即即使找到了target，也要删去右边/左边的一半元素，一直到最终结束为止。

与这一个题目思路类似的就是Leetcode 410，这一个题也是找到上下限之后通过二分去找答案，我们也不多说了。

Problem 5: Leetcode 4 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

这一个题是非常经典的一道hard，同时也是一道高频题（我就被考过……）。所以固然，解决这个问题需要一些技巧。

对于这一个题，我们已经有了有序的条件，所以还需要看如何才能消去一半的元素。事实上，中位数就是中间的数，所以我们其实可以考虑再抽象一下问题，考虑直接求解“第

小的数"。对于这个情况，我们可以考虑在两个数组中都切割出一半的元素，也就是

。

现在假如说两个数组分别是A, B，那么考虑位置A[k/2 - 1], B[k/2 - 1]，那么如果有A[k/2 - 1] <= B[k/2 - 1]（这里要注意判断一下等于号的情况，在这个题中，它可以和小于号归为一种情况讨论，但之前的题目不是），那么事实上，可以保证的是，A[k/2 - 1]之前的所有元素都会比它小（一共

个），而B[k/2 - 1]之前的元素最多有

个比它小（想想为什么？），换句话说，加在一起也就

个元素比它小，也就是说A[k/2 - 1]及其之前的元素都不会是第

小的元素，那么就直接删去其左半部分即可。

反过来，如果是A[k/2 - 1] > B[k/2 - 1]，那么对应的，删去B[k/2 - 1]及其之前的元素就可以了。这样的话，每次都会消去一半，二分的意思就到了。

当然了这一个题的细节是很多的，比方说

，或者越界（超过数组长度），以及其中一个数组被删空等等。对于第一个情况，只有可能是

，那就直接返回两个数组第一个元素中较小的那一个就好了。对于第三个也很简单，直接在第二个数组中返回对应的第

小就可以了。对于第二个情况，处理的时候要稍微小心一点，既然越界了，那么最多也只能删去所有的元素了，但是这个时候要注意，这个时候就不再是“消去一半”了，所以需要对下一步迭代，到底要找第几大的元素，按照实际消去的情况作修改。

好的，我们来放出核心代码。

int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
  int m = nums1.size();
  int n = nums2.size();
  int index1 = 0, index2 = 0;

  while (true) {
    // 边界情况（第3个情况）
    if (index1 == m) {
      return nums2[index2 + k - 1];
    }
    if (index2 == n) {
      return nums1[index1 + k - 1];
    }
    if (k == 1) { // 第1个情况
      return min(nums1[index1], nums2[index2]);
    }

    // 正常情况（第2个情况）
    int newIndex1 = min(index1 + k / 2 - 1, m - 1);
    int newIndex2 = min(index2 + k / 2 - 1, n - 1);
    int pivot1 = nums1[newIndex1];
    int pivot2 = nums2[newIndex2];
    if (pivot1 <= pivot2) {
      k -= newIndex1 - index1 + 1;
      index1 = newIndex1 + 1;
    }
    else {
      k -= newIndex2 - index2 + 1;
      index2 = newIndex2 + 1;
    }
  }
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  int totalLength = nums1.size() + nums2.size();
  if (totalLength % 2 == 1) {
    return getKthElement(nums1, nums2, (totalLength + 1) / 2);
  }
  else {
    return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
  }
}

当然，还有一个细节，就是中位数的定义。如果数组长度和为偶数，需要找到两个中间值，再求个平均。

Problem 6: Leetcode 287 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。 你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

这个问题其实更像是一个位运算主题的题目。不过它的二分方法确实比较巧妙，我们也拿来说一下。

我们可以从简单的情况开始看起，假如说重复的数只重复两次，那么数组中一定1-n全部都有，这样的话，有一个性质在于，对于一个固定的数

，我们对数组求满足

的元素个数，记为

（例如对于数组[1, 2, 3, 3, 4]，有

），那么可以发现，在遇到了这个重复的数之前，都有

，但是遇到了这个重复的数之后，就有

。这样，二分的目的就明确了，我们设置好上下限（这里就是

）之后，观察mid，如果mid这个位置上，

，说明这个重复的元素在数组右边，那就应该删去左半部分的元素。反过来自然不必多说了。

但是这里我们是假设只重复两次的，但是如果重复不止两次，1-n就不一定全部存在，这个时候还能够这么考虑吗？我们不妨考虑一个例子[1, 2, 3, 3, 3, 4]，那么这样的话，可以算出

，[1, 2, 4, 5, 5, 5, 6]，我们也可以算出类似的值。因此实际上可以看出，对于一般的情况，我们也可以利用相同的策略，无非就是可能

变成了

罢了。

好的，我们来放出这一个题目的核心代码。

int findDuplicate(vector<int>& nums) {
  int n = nums.size();
  int l = 1, r = n - 1, ans = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      cnt += nums[i] <= mid; // nums[i] <= mid才记录
    }
    if (cnt <= mid) {
      l = mid + 1;
    } else {
      r = mid - 1;
      ans = mid;
    }
  }
  return ans;
}

好的，关于二分的题目，我们就先说这么多。

算法3：排序算法（上）

排序（sorting）算法是一个非常大的门类。冒泡排序，归并排序，快速排序，堆排序等都比较容易出比较有趣（也比较难想）的题目。

在这之前，我们简单介绍一下归并排序。核心目的在于分治+归并的思想。也就是说，我们会写出一个递归出来，对于左半部分和右半部分分开递归执行归并排序。递归完成之后，我们得到的元素，就是左右两边各自有序的，所以只需要再做一次“归并”，就可以使得全数组有序。这个归并的方式可以见下图。

非常好理解，对吧？

当然实际的问题中，使用归并思想的题目更为常见，而不仅仅是考察归并排序这一个算法应该怎么写。所以这一部分我们拿几个归并排序的算法变种题，来结束这一节。

Problem 7: Leetcode 315 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质：counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

比方说nums = [5, 2, 6, 1]，那么最终就应该输出[2, 1, 1, 0]。比方说对于第一个5而言，它右边有两个元素比它小，所以对应的位置填2。

对于这个题，其实我们可以考虑一个更简单一点的情况。考虑把nums拆分成两个数组，一个前一半数组A一个后一半数组B。也即当数组A, B都是有序数组的时候，我们有什么办法可以解决这个问题？

这里我们举一个例子，考虑A = [8, 12, 16, 22, 100], B = [7, 7, 7, 26, 55, 64, 91]，那么容易知道，对于8来说，右边有3个元素比它小，而对于100来说，右边有7个元素比它小，我们怎么知道这些结果呢？不妨考虑这个“归并”的过程。注意到两个指针一定会在排序的时候经过下面这一个状态。

也就是说一开始的时候，都是B的指针在移动，而A的指针如果移动了，说明目前B指针所在位置之前的所有的B的元素，都是比A之前那个元素要小的，所以都应该被记录在答案中。比方说图中的状态，我们发现，指针从A里的元素8移动的时候，B指针左边正好有3个元素，说明“右边有3个元素比这个8要大”，因此答案应该加3。

因此总结一下，首先我们因为需要左半部分和右半部分为两个有序数组，所以需要进行归并排序。其次我们需要利用这两个部分数组，去统计每一个元素对应的答案，所以要修改归并排序中，递归的部分结束之后的模块。因为有递归的存在，所以我们虽然只统计了B中，比A中元素小的元素个数，但是不用担心A中右边元素比A中左边的元素小的元素个数的情况，因为这已经在递归中被计算过了。

这里还有一个细节，就是我们在排序中，会改变元素的顺序。所以还需要记录一下排序之前每一个元素对应的一开始的元素下标，这样的话结果统计的时候就不会出错。这里举一个例子：

这一段解释还是有些复杂的，大家可以结合着代码看一下。

public List<Integer> countSmaller(int[] nums) {
  this.index = new int[nums.length];
  this.temp = new int[nums.length];
  this.tempIndex = new int[nums.length];
  this.ans = new int[nums.length];
  for (int i = 0; i < nums.length; ++i) {
    index[i] = i;
  }
  int l = 0, r = nums.length - 1;
  mergeSort(nums, l, r);
  List<Integer> list = new ArrayList<Integer>();
  for (int num : ans) {
    list.add(num);
  }
  return list;
}

public void mergeSort(int[] a, int l, int r) {
  if (l >= r) {
    return;
  }
  int mid = (l + r) >> 1;
  mergeSort(a, l, mid);
  mergeSort(a, mid + 1, r);
  merge(a, l, mid, r);
}

public void merge(int[] a, int l, int mid, int r) {
  int i = l, j = mid + 1, p = l;
  while (i <= mid && j <= r) {
    if (a[i] <= a[j]) {
      temp[p] = a[i];
      tempIndex[p] = index[i];
      ans[index[i]] += (j - mid - 1);
      ++i;
      ++p;
    } else {
      temp[p] = a[j];
      tempIndex[p] = index[j];
      ++j;
      ++p;
    }
  }
  while (i <= mid)  {
    temp[p] = a[i];
    tempIndex[p] = index[i];
    ans[index[i]] += (j - mid - 1);
    ++i;
    ++p;
  }
  while (j <= r) {
    temp[p] = a[j];
    tempIndex[p] = index[j];
    ++j;
    ++p;
  }
  for (int k = l; k <= r; ++k) {
    index[k] = tempIndex[k];
    a[k] = temp[k];
  }
}

换了Java是因为题解里面没有C++，我又比较懒，所以就粘贴过来了……核心的过程和C++差距不大。

这一个题其实由剑指offer的51拓展过来，感兴趣的读者可以再去看看这一个题，思路几乎完全相同。

Problem 8: Leetcode 493 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。

对于这一个题，可以看出还是一样，要找到翻转对。本质上和逆序对（剑指offer 51）的做法是没差的，我们细说一下。

在这里，我们也可以假设有两个有序的数组A, B，并且假设

分别为A, B对应的指针位置。然后一开始移动B中的指针

，当nums[i] <= 2*nums[j]，并且nums[i] > 2*nums[j-1]时，可以看出，

前面的所有的B的元素，都是与A目前所指向的元素为翻转对的，因此答案需要加上

。然后再将

向右移动1格，重复上面的操作即可。由于我们需要有序数组，所以这个过程可以通过归并排序来实现。

好的，我们来看看核心代码。

if (left == right) {
  return 0;
} else {
  int mid = (left + right) / 2;
  int n1 = reversePairsRecursive(nums, left, mid);
  int n2 = reversePairsRecursive(nums, mid + 1, right);
  int ret = n1 + n2;

  // 首先统计下标对的数量
  int i = left;
  int j = mid + 1;
  while (i <= mid) {
    while (j <= right && (long long)nums[i] > 2 * (long long)nums[j]) j++;
    ret += (j - mid - 1);
    i++;
  }

  // 随后合并两个排序数组
  vector<int> sorted(right - left + 1);
  int p1 = left, p2 = mid + 1;
  int p = 0;
  while (p1 <= mid || p2 <= right) {
    if (p1 > mid) {
      sorted[p++] = nums[p2++];
    } else if (p2 > right) {
      sorted[p++] = nums[p1++];
    } else {
      if (nums[p1] < nums[p2]) {
        sorted[p++] = nums[p1++];
      } else {
        sorted[p++] = nums[p2++];
      }
    }
  }
  for (int i = 0; i < sorted.size(); i++) {
    nums[left + i] = sorted[i];
  }
  return ret;

最终需要执行的就是reversePairsRecursive(nums, 0, nums.size() - 1)。

一个和这个题目很像的是Leetcode 327，读者可以使用这个题作为练习。

好的，关于归并排序的变种，我们就写到这里。

小结

本节我们主要介绍了二分查找算法和排序算法中，归并排序的一些变种习题。每一道习题的答案都并不是二分查找或者归并排序的直接应用，而是将他们的思想抽丝剥茧，通过对算法的细微修改而得到的。尤其对于归并排序的这一个技巧，在很多经典题中都有应用，本质上是合并排序的过程+利用有序数组完成重要的统计步骤。当然也是因为代码难度的制约，它对应的很多题都是hard，可能需要读者花时间去好好思考。

下一节我们会继续介绍排序算法相关的题目，包括堆，快速选择算法等由此衍生出来的算法与数据结构。