在两个长度相等的排序数组中找到上中位数（二分法、尾递归、牛客网）+1

目录

• 1 题目描述
• 2 解题（Java）
• 3 复杂性分析

1 题目描述

给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。

上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数

要求
时间复杂度为O(logN)，额外空间复杂度为O(1)

示例1

输入

[1,2,3,4],[3,4,5,6]

返回值

3

说明

总共有8个数，上中位数是第4小的数，所以返回3。

示例2

输入

[0,1,2],[3,4,5]

返回值

2

说明

总共有6个数，那么上中位数是第3小的数，所以返回2

备注:

1 <= N <= 10 ^ 5
0 <= arr1i, arr2i <= 10 ^ 9

2 解题（Java）

2.1 解题思路

1. 求中位数，其实就是求第k小数的一种特殊情况；假设要找两个数组中的第k小数，可以使用二分法每次循环排除掉k / 2个数，正满足了时间复杂度O(logN)；
2. 由于定义的递归函数属于尾递归，因此空间复杂度为O(1);

详细解答可参考：

https://blog.csdn.net/sc179/article/details/110490303

2.2 代码

import java.util.*;
public class Solution {
    /**
     * find median in two sorted array
     * @param arr1 int整型一维数组 the array1
     * @param arr2 int整型一维数组 the array2
     * @return int整型
     */
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        int k = arr1.length;
        return getKth(arr1, 0, k - 1, arr2, 0, k-1, k);
    }
    int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        
        if (len1 == 0) return nums2[start2 + k - 1];
        if (len2 == 0) return nums1[start1 + k - 1];
        
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);
        
        int start1_new = start1 + Math.min(len1, k / 2);
        int start2_new = start2 + Math.min(len2, k / 2);
        
        if (nums1[start1_new - 1] > nums2[start2_new - 1]) {
            return getKth(nums1, start1, end1, nums2, start2_new, end2, k - Math.min(len2, k / 2));
        }
        else {
            return getKth(nums1, start1_new, end1, nums2, start2, end2, k - Math.min(len1, k / 2));
        }
    }
}

3 复杂性分析

• 时间复杂度O(logN)：每进行一次循环，就减少k/2个元素；
• 空间复杂度O(1)：虽然用到了递归，但可以看到这个递归属于尾递归，编译器不需要不停地堆栈，所以空间复杂度为O(1)；