解题思路

这个题目是说在两个已排序的数组中找到中间的数，并且要求复杂度是O(ln(m+n))。看到这个复杂度要求，就不能使用简单的数组合并后取中间位置，而是要考虑类似二分法之类的算法。

算法的要点就是把题目转换成寻找第k个位置的数字，对于数组A和B，假设都长度都大于k/2,那么都取k/2的位置进行比较，假设A[k/2]小于B[k/2]，那么A中k/2之前的位置都不可能是第k个位置，那么可以直接排除，问题转换成在A的k/2位置之后组成的数组和B数组中，寻找第k-k/2位置的数字。以此类推，就是一个递归实现了。

参考源码

public class Solution {    public double findMedianSortedArrays(int[] nums1, int[] nums2) {        int total = nums1.length + nums2.length;        if (total % 2 == 0) {            return (findKth(total / 2, nums1, 0, nums2, 0) + findKth(total / 2 + 1, nums1, 0, nums2, 0)) / 2.0;        } else {            return findKth(total / 2 + 1, nums1, 0, nums2, 0);        }    }    private int findKth(int k, int[] nums1, int s1, int[] nums2, int s2) {        if (s1 >= nums1.length) {            return nums2[s2 + k - 1];        }        if (s2 >= nums2.length) {            return nums1[s1 + k - 1];        }        if (k == 1) {            return Math.min(nums1[s1], nums2[s2]);        }        int k1 = s1 + k / 2 - 1 < nums1.length ? nums1[s1 + k / 2 - 1] : Integer.MAX_VALUE;        int k2 = s2 + k / 2 - 1 < nums2.length ? nums2[s2 + k / 2 - 1] : Integer.MAX_VALUE;        if (k1 < k2) {            return findKth(k - k / 2, nums1, s1 + k / 2, nums2, s2);        } else {            return findKth(k - k / 2, nums1, s1, nums2, s2 + k / 2);        }    }}