【力扣刷题】二分查找：4. 寻找两个正序数组的中位数

题目：

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

算法的时间复杂度应该为 O(log (m+n)) 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays

解题思路：

题目难度主要是在时间复杂度上面，O(log(m+n))，我一开始是用的双指针来实现的，两个指针分别指向两个数组的初始位置，因为两个数组都是已知且有序的，则长度也已知，所以只需要找到中点位置(奇数个元素)，或者是中点的两个元素除以2（偶数个元素），则使用双指针很方便，但是时间复杂度就不会满足了，为O(m+n)，所以要达到题目要求的时间复杂度，得想另一种实现方式，二分法->二分查找。

因为数组是有序的，可以实现一半一半的排除，假如我们要找第k小的数字，我们比较两个数组的第k/2的位置的数字大小，如果其中一个更小，那么它和它前面的数字都不会是第k小的数字，则都可以排除。

例子：

数组A：1，3，4，9

数组B：1，2，3，4，5，6，7，8，9，10

过程：

因为n1 = 4，n2 = 10，所以要找的中点元素为第7个和第8个元素的和除以2。找第7小的元素过程如下：

①A中比k小的有k/2-1个，B中有k/2-1个，这时4>3，说明B中1，2，3（前k/2个元素）都可以排除

②已经排除了三个元素，在两个新数组中，只需要找剩下的元素的第4小的元素。则k=7-3=4，k/2=2，比较两个k/2处的元素，较小的那一处可以排除。这时5>3，则排除A的元素1，3

③又排除了A数组中的前面两个元素1，3，那么剩下的元素k=4-2=2，k/2=1，继续判断k/2处的元素，4==4，排除哪个都可以，去掉一个还是会保留一个元素的。

④那就排除下面的数组元素，然后又排除了一个元素，k=2-1=1，则比较两个数组的元素，较小的那个元素则所求。

⑤其实算法找第奇数还是第偶数个小的数字，不会影响算法的整体，只需要把传的参数改为k=8就可以了，在算法进行中，k 的值都有可能从奇数变为偶数，最终都会变为 1 。

⑥特殊情况，在排除元素的过程中，会遇到数组元素长度小于k/2的情况，那这种时候，只需要将指针的箭头指向该数组的末尾元素，再进行比较，如果小于，则直接排除，相当于找另一个数组里面剩余的k-length的元素即可。

代码：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        int left = (n1 + n2 + 1)/2;
        int right = (n1 + n2 + 2)/2;
        //将元素总数是奇数/偶数的情况统一，如果为奇数，就求两次一样的值的和除以2
        return (getK(nums1,nums2,left,0,n1-1,0,n2-1)+getK(nums1,nums2,right,0,n1-1,0,n2-1))/2;
    }
    public double getK(int[] nums1,int[] nums2,int k,int start1,int end1,int start2,int end2){
        int leng1 = end1 - start1 + 1;
        int leng2 = end2 - start2 + 1;
        //如果有元素数组为空了，那就直接从另外一个数组中寻找要求的值
        if(leng1 == 0) return nums2[start2 + k - 1];
        if(leng2 == 0) return nums1[start1 + k - 1];
        //k==1，那么就比较两个元素中较小的那个，返回小的元素
        if(k == 1) return Math.min(nums1[start1],nums2[start2]);
        
        //递归，每次比较剩余元素数组k/2处的元素，小的部分全部排除
        //要注意比较剩下的元素是否还有k/2个元素，没有的话直接将指针赋值到数组尾元素
        int i = start1 + Math.min(leng1,k/2) - 1;
        int j = start2 + Math.min(leng2,k/2) - 1;
        if(nums1[i] >= nums2[j]){
            return getK(nums1,nums2,k-(j-start2+1),start1,end1,j+1,end2);
        }else{
            return getK(nums1,nums2,k-(i-start1+1),i+1,end1,start2,end2);
        }
        }
}

递归终止的条件就是某一个数组为空或者k==1的时候，则根据不同情况返回不同的值即可，元素总数个数为奇数的时候，则求两次（left和right值相同）一样的值相加除以2；为偶数就求left和right对应的值的和除以2，返回即可。