LeetCode解析------4.寻找两个正序数组的中位数-二分查找

题目：

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

简单介绍：
题目：寻找两个正序数组的中位数
题目难度：困难
使用语言：JAVA
这道题来自leetcode题库的二分查找标签。

解题思路：
首先看题、分析题意，我们可以明确1个关键点：
1.处理两数组 长度之和为偶数 与 长度之和为奇数 的情况
既然，我们已经分析出来题目的关键任务了，下面我们就可以开始思考实现了。
我们采用算法与数据结构的思路来剖析一下这题

数据结构：
要实现对数据的操作，我们要先明确存储数据的数据结构。
该题的数据结构的作用：
1.无需数据结构，递归调用即可

算法：
既然明确了我们的数据结构，我们就可以开始我们的算法分析了。
1.第一步，初始化工作（处理奇数和偶数的情况）。
2.第二步，编写递归函数。

代码部分：

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1=nums1.length;
        int len2=nums2.length;

        //奇数和偶数的情况都可以满足,求第K个小的数
        int left=(len1+len2+1)/2;
        int right=(len1+len2+2)/2;
        return (findMedian(nums1,0,len1-1,nums2,0,len2-1,left)+findMedian(nums1,0,len1-1,nums2,0,len2-1,right))*0.5;


    }

    double findMedian(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){
        int len1=end1-start1+1;
        int len2=end2-start2+1;

        //保证len1小于len2
        if(len1>len2) return findMedian(nums2,start2,end2,nums1,start1,end1,k);
        //返回nums2的中位数
        if(len1==0) return nums2[start2+k-1];

        //K==1说明到了中位数的位置
        if(k==1) return Math.min(nums1[start1],nums2[start2]);

        //移除小于中位数的元素
        //中位数的左边的数都小于中位数，右边的数都大于中位数
        int i=start1+Math.min(len1,k/2)-1;
        int j=start2+Math.min(len2,k/2)-1;

        //比较中位数
        if(nums1[i]>nums2[j]){
            return findMedian(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));//去掉nums2的小于中位数的元素
        }
        else{
            return findMedian(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));//去掉nums1的小于中位数的元素
        }
    }
}

时间、空间复杂度：

结语：
晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！