力扣 4. 寻找两个正序数组的中位数

使用归并的方式合并两个有序数组，并找出中位数：

通过归并排序合并两个数组，然后直接根据合并后数组的长度计算中位数。

class Solution {public double findMedianSortedArraysMerge(int[] nums1, int[] nums2) {int[] merged = new int[nums1.length + nums2.length];int i = 0, j = 0, k = 0;// 归并排序的合并过程while (i < nums1.length && j < nums2.length) {if (nums1[i] < nums2[j]) {merged[k++] = nums1[i++];} else {merged[k++] = nums2[j++];}}// 如果有剩余元素，直接复制到 merged 数组while (i < nums1.length) {merged[k++] = nums1[i++];}while (j < nums2.length) {merged[k++] = nums2[j++];}// 计算中位数if (merged.length % 2 == 0) {return (merged[merged.length / 2] + merged[merged.length / 2 - 1]) / 2.0;} else {return merged[merged.length / 2];}}
}

不合并数组，直接找到中位数的位置：

通过两个指针在两个数组中移动，直到找到中位数的位置。

class Solution {public double findMedianSortedArraysDirect(int[] nums1, int[] nums2) {int totalLength = nums1.length + nums2.length;int count = 0, i = 0, j = 0;int a = 0, b = 0; // 用于存储中间位置的数while (count <= totalLength / 2) {a = b; // 存储上一轮的 b，当总长度是偶数时需要用到// 移动指针，找到中位数的位置if (i < nums1.length && (j >= nums2.length || nums1[i] < nums2[j])) {b = nums1[i];i++;} else {b = nums2[j];j++;}count++;}// 根据总长度是奇数还是偶数，计算中位数if (totalLength % 2 == 0) {return (a + b) / 2.0;} else {return b;}}
}

二分查找：

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 计算两个数组的总长度int length1 = nums1.length, length2 = nums2.length;int totalLength = length1 + length2;// 判断总长度是奇数还是偶数，以决定如何计算中位数if (totalLength % 2 == 1) {// 如果是奇数，直接找到中间位置的数int midIndex = totalLength / 2;return getKthElement(nums1, nums2, midIndex + 1);} else {// 如果是偶数，找到中间两个数，计算平均值int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;return (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;}}// 主要逻辑方法，用于找到两个排序数组中的第 k 小的数public int getKthElement(int[] nums1, int[] nums2, int k) {int length1 = nums1.length, length2 = nums2.length;int index1 = 0, index2 = 0;while (true) {// 处理边界情况if (index1 == length1) {return nums2[index2 + k - 1];}if (index2 == length2) {return nums1[index1 + k - 1];}if (k == 1) {return Math.min(nums1[index1], nums2[index2]);}// 正常情况，比较两个数组中的第 k/2 个元素int half = k / 2;// 新的索引位置，不能超过数组长度int newIndex1 = Math.min(index1 + half, length1) - 1;int newIndex2 = Math.min(index2 + half, length2) - 1;int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];// 比较并更新索引，减少 k 的值if (pivot1 <= pivot2) {k -= (newIndex1 - index1 + 1);index1 = newIndex1 + 1;} else {k -= (newIndex2 - index2 + 1);index2 = newIndex2 + 1;}}}
}

让我们一步步分析这段代码和其中的逻辑，以便更好地理解如何通过二分查找达到 O(log(m + n)) 的时间复杂度。

这个算法的关键在于每次迭代排除 (k/2) 个元素，而不是逐个排除，从而将时间复杂度降低到对数级别。

初始条件：我们有两个排序数组 nums1 和 nums2，以及一个目标值 k，表示我们需要找到两个数组合并后的第 k 个元素。
二分查找的核心：在每一轮迭代中，我们比较 nums1[k/2 - 1] 和 nums2[k/2 - 1]。根据二分查找的策略，我们可以排除较小值所在数组的前 k/2 个元素。
边界条件处理：
- 如果 nums1 或 nums2 为空，直接从另一个数组中返回第 k 个元素。
- 如果 k == 1，返回 nums1[0] 和 nums2[0] 中的较小值。
- 如果 nums1[k/2 - 1] 或 nums2[k/2 - 1] 越界，我们应选择相应数组的最后一个元素进行比较。
递归或迭代：根据比较结果，我们排除一部分元素。例如，如果 nums1[k/2 - 1] < nums2[k/2 - 1]，那么我们可以安全地排除 nums1 的前 k/2 个元素。接下来，我们更新 k 的值为 k - k/2，继续在剩下的元素中查找。
更新索引和 k 的值：根据排除的元素数量更新 index1 或 index2，同时减少 k 的值，因为我们已经排除了一些元素，所需查找的位置也相应地减少。

通过这种方式，每次迭代我们至少排除 k/2 个元素，这就是算法能达到 O(log(m + n)) 时间复杂度的原因。每一轮迭代后，k 的值都会减半，最终在对数次迭代后达到递归基。这种方法避免了直接合并数组，从而大大提高了效率。

在这段代码中，findMedianSortedArrays 方法首先判断总长度是奇数还是偶数，并相应地调用 getKthElement 方法找到中位数或两个中位数的平均值。getKthElement 方法通过二分查找的方式逐渐缩小搜索范围，直到找到第 k 小的元素。通过每次排除掉 k/2 个元素，该方法有效地将时间复杂度降低到了O(log(m+n))。