Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

难度：hard

Solution: Binary Search

用binary search的方式去除小于中位数的一部分元素，逐步缩小检索的范围。这个问题可以变形为找到第K个元素。在很多处理排序数组的问题时都可能用到binary search。

public class Solution {
    private int findKthSmallest(int[] a, int p, int m, int[] b, int q, int n, int k) {
        // in this way, only a's index need to be checked.
        if(m > n) {
            return findKthSmallest(b, q, n, a, p, m, k);
        }
        if(m == 0) {
            return b[q + k - 1];
        }
        if(k == 1) {
            return Math.min(a[p], b[q]);
        }
        // the length sum must be k.
        int aHalf = Math.min(m, k / 2);
        int bHalf = k - aHalf;
        if(a[p + aHalf - 1] < b[q + bHalf - 1]) {
            return findKthSmallest(a, p + aHalf, m - aHalf, b, q, n, k - aHalf);
        } else if(a[p + aHalf - 1] > b[q + bHalf - 1]) {
            return findKthSmallest(a, p, m, b, q + bHalf, n - bHalf, k - bHalf);
        } else {
            return a[p + aHalf - 1];
        }
    }
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        if(total % 2 != 0) {
            return findKthSmallest(nums1, 0, m, nums2, 0, n, total / 2 + 1);
        } else {
            return (findKthSmallest(nums1, 0, m, nums2, 0, n, total / 2) + findKthSmallest(nums1, 0, m, nums2, 0, n, total / 2 + 1)) / 2.0;
        }
    }
}