知识点

二分查找

思路

要寻找第k个数字，分别找到两个数组中的第k/2数字，较小的这部分可以说明答案不在里面，将这部分排出查找范围，一步步缩小范围直到找到答案

时间复杂度

由于每次可以排除k/2，也就是一半，所以是O(log(m+n))

代码

使用语言：java

import java.util.*;


public class Solution {
    public double findMedianSortedArrays (int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0) return n % 2 == 0 ? (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0 :
                               nums2[n / 2];
        if (n == 0) return m % 2 == 0 ? (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0 :
                               nums1[m / 2];

        int total = m + n;
        if (total % 2 == 0) return (findKth(nums1, 0, nums2, 0,
                                                total / 2) + findKth(nums1, 0, nums2, 0, total / 2 + 1)) / 2.0;
        else return findKth(nums1, 0, nums2, 0, total / 2 + 1);
    }
  	// 寻找第k个数，begin为数组起始位置
    double findKth(int[] a, int a_begin, int[] b, int b_begin, int k) {
	  	// 边界条件
	  	// 如果一个数组起始位置超过长度，则只能在另一个数组找
        if (a_begin >= a.length) return b[b_begin + k - 1];
        if (b_begin >= b.length) return a[a_begin + k - 1];
        if (k == 1) return Math.min(a[a_begin], b[b_begin]);

	  	// 第k/2个数是否超过数组长度，是的话则表明无法取到，无法进行比较，即begin不变，见34行
        int mid_a = Integer.MAX_VALUE;
        int mid_b = Integer.MAX_VALUE;
        if (a_begin + k / 2 - 1 < a.length) mid_a = a[a_begin + k / 2 - 1];
        if (b_begin + k / 2 - 1 < b.length) mid_b = b[b_begin + k / 2 - 1];

        // 比较第k/2个数
        if (mid_a < mid_b) {
		  	// 可以确定第k个数不在a[begin...begin+k/2-1]中，将其排除，由于排除了k/2个数，所以要找的数变为第k-k/2个
            return findKth(a, a_begin + k / 2, b, b_begin, k - k / 2);
		  	// 
        } else return findKth(a, a_begin, b, b_begin + k / 2, k - k / 2);
    }
}