image.png

由于时间的要求，肯定使用二分法解决。最开始我的思路是两个数组的判断两个数组的中间值，假设m1，m2。如果m1<m2,那么m1左边和m2右边的数肯定不存在最终解，那么就都删除掉，继续递归。这样每次删除一些干扰的数。
由于奇数偶数的问题，中间的数可能是一个或两个，最终每个数组剩下可能已一个数或者两个数。在对这几个数排序求中间值就可以。我认为每次删除一半的数据相当于整体做二分查找。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int start1=0,end1=nums1.length-1;
        int start2=0,end2=nums2.length-1;

        if(end1<0 && end2<0)
            return 0.0;
        if(nums1.length==0){
            return nums2.length%2>0?nums2[end2%2]:(nums2[end2/2]+nums2[end2/2+1])/2.0;
        }
        if(nums2.length==0){
            return nums1.length%2>0?nums1[end1/2]:(nums1[end1/2]+nums1[end1/2+1])/2.0;
        }
        //判断是否都就剩2个或1个数
        while (end1-start1>1 || end2-start2>1){
            int middle1=nums1[(start1+end1)/2];
            int middle2=nums1[(start2+end2)/2];
            if(middle1>middle2){
                end1=middle1;
                start2 = middle2;
            }else {
                start1 = middle1;
                end2 = middle2;
            }
        }

        List<Integer> list = new ArrayList<>();
        list.add(nums1[start1]);
        list.add(nums2[start2]);
        if(start1 != end1){
            list.add(nums1[end1]);
        }
        if(start2 != end2){
            list.add(nums2[end2]);
        }

        //对最后剩下的数排序求解
        List<Integer> collect = list.stream().sorted().collect(Collectors.toList());
        if(collect.size()%2 == 0){
            return (collect.get(collect.size()/2) + collect.get(collect.size()/2-1))/2.0;
        }else {
            return collect.get(collect.size()/2)*1.0;
        }
    }

但是非常不幸，最后时间不符合要求。看了网上其他一写文章，思路不一样。
思想可以参考
思路
简洁代码
大概的思路是如果两个数组求第K个数，那么把k分成两份，第一个数组前K/2个数小于第一个数组所有后面的数(理所当然)且小于第二个数组后面的数，同理第二个数组前K/2个数也是小于两个数组的后面的数。这样两个数组的两个K/2个数相加，正好就是所求第K个数。
如果不满足，说明一个分多了，一个分少了。所以应该分少的那个数组的前K/2个数就可以舍去，递归找两个数组的K-K/2个数。

思路转换的关键是二分不仅可以把数组二分，还可以把要查找第几个值二分。