“你走过的路，只是别人走过的路。

image

相信看了这个标题的同学，对这道题以已经非常不陌生了，就是leecode当中的第四题，之所以要单独的写一写主要对我来说，里面涉及到比较重要的知识点：二分法，同时也提供了几道简单的练习题（后面也会遇到），就比较容易懂了。这道题也曾被Apple, Micosoft, Amazon, Zenefits, Yahoo, Dropbox, Adobe作为经典面试题。

题目

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数（是按顺序排列的一组数据中居于中间位置的数） ，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。

示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0

示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5

简单说一下要求时间复杂度为O(log(m + n)),就是想让我们利用二分法来解答，这里简单说一下二分法：

比如123456789，你要找2，首先查中间元素5，大于2，所以直接排除掉5右边的6789，然后在1234里继续二分查找。每次排除1/2的元素，所以是O(log2n)。简单推导一下：

推导

总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。 由于n/2^{k取整后>=1（最坏的情况是二分到只剩下一个），即令n/2}k=1-> 2^K = n，可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)。

热身一下，做几个简单练习题

①二分法练习1：寻找一个数

说白了，就是在一个有序数组中，给出一个目标数，二分找到这个数。

参考代码

int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意

  while(left <= right) {
      int mid = left + (right - left) / 2; // 3 1
      if(nums[mid] == target) // 是否是中间
          return mid;
      else if (nums[mid] < target) // 去掉了中间，肯定就在两边，如果中间<target 就在右边，从右边开始
        left = mid + 1; // 注意
      else if (nums[mid] > target)
        right = mid - 1; // 注意
  }
  return -1;
}

 @Test
   public void isbinarySearch() {
   int[] nums = {1,2,2,2,3};
   int i = binarySearch(nums,4);
   Assert.assertNotNull(i);
 });  }

image

②二分法练习2：寻找左侧边界的二分搜索

简单的说，找到了目标值，如果有多个目标值，取最左边的一个值。

参考代码

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = left + (right - left) / 2; // 3 1
        if (nums[mid] == target) { // 找左边就缩小右边
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

@Test
public void isleft_bound() {
    int[] nums = {1, 2, 2, 2, 3};
    int i = left_bound(nums, 2);
    Assert.assertNotNull(i);
}

简单分析一下，相对前面那道题，这道题提高了一点难度

1. 因为要找到最左侧的目标值，时间复杂度为logn,它的循环条件是left < right,如果相等的话会超出时间限制。

2. 找到目标值，现在不能直接返回，需要找到最左侧的目标值，可以缩小右侧，令right = mid, 这里不能是right = mid -1，因为这个时候本来target = mid,如果right就是最左侧的目标值可能就会有问题了。

回到本题

做的这两道的训练题，对理解这道题很有帮助的。

求中位数，需要判断总长度的奇数偶数，如果是奇数直接取中位数，如果是偶数取中间两个数/2为中位数。

根据事例提出两个问题：

①是否能将两个数组二分为一个数组

②如果有些情况不能二分为一个数组（比如一个数组只有一个数但是数很大），当对两个数组之和二分至1的时候，排出了较小数之后，取两数组的最小值为中 位数。

image

针对第一个问题，事例1：

A: 1 2

B: 1 2 3 4 5 6 7 8 9 10

我们定义两个数组的索引，当A数组的索引index1等于A数组的length1,直接取B数组的索引+k(二分的mid) -1。

如果让index1=length1,说明A数组的所有值都作为较小值给排除掉了。

首先我们知道k=(length1+length2) + 1=7这是总长度的mid，我们对需要每个数组的mid然后比较排除较小的，所以k = k/2=3，我们知道A的长度是2，这里如果取A数组长度为3的值就会越界，所以我们取length1就行，

比较大小排除较小值，获取A数组的length1的值为2,获取B数组长度为3的值是3，因为2<3,直接排除A数组1~length的长度：令index1 = length，接下来计算k：

这里我们A数组长度为3越界了：k = k -length - index1 -1，如果没有越界就是k = k -k/2.

image

int index1 = 0, index2 = 0; // 初始化索引  
if (index1 == length1) {
      return nums2[index2 + k - 1]; // 因为是计算的length，所以对应数组下标进行-1
}

事例2:

A: 1 2 3 4 5 6 7 8 9 10

B: 1 2

相反，这里我直接给出结论。我们定义两个数组的索引，当B数组的索引index2等于B数组的length2,直接取A数组的索引+k(二分的mid) -1。

image

 if (index2 == length2) {
     return nums1[index1 + k - 1];
 }

事例3：

A: 100 200

B: 1 2 3 4 5 6 7 8 9

对于这样的数组，我们是不能直接合成一个数组的，但是我们可以通过不断的二分，排除较小值，当k=1时，剩下的谁最小谁就是中位数。

简单分析一下，一共11个数，第6个数为mid,对mid除以2，得到half=3,长度为3的A数组越界，取length1=200>3,排除掉B数组的1, 2, 3 三个数，更新k=k-k/2 =6-3=3,index2=3

image

继续获取half = k/2=1,对A数组length=1的值为100，B数组对应的length=index2+half=4的值为4，因为100>4, 排除掉B数组的4,更新k=k-k/2=3-1=2,index2=4

image

继续获取half=1,对A数组length=1的值为100，B数组对应的length=index2+half=5的值为5，因为100>5, 排除掉B数组的5,更新k=k-k/2=2-1=1,index2=5

image

当k=1时，获取A[1]=100,B[5]=6,因为100>6,所以6就是我们的中位数。

   if (k == 1) { 
      return Math.min(nums1[index1], nums2[index2]);
   }

事例4：

A: 1 2 3 4 5 6 7 8 9

B: 1 2 3 4 5 6 7 8 9

本事例可按照事例3分析，留着看官分析吧。

参考代码

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int length1 = nums1.length, length2 = nums2.length;
    int totalLength = length1 + length2;
    if (totalLength % 2 == 1) { // 奇数
        int midIndex = totalLength / 2;
        double median = getKthElement(nums1, nums2, midIndex + 1);
        return median;
    } else {//
        int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
        double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
        return median;
    }
}

public int getKthElement(int[] nums1, int[] nums2, int k) {
    int length1 = nums1.length, length2 = nums2.length;
    int index1 = 0, index2 = 0; // 初始化索引
    int kthElement = 0;

    while (true) {
        // 边界情况
        if (index1 == length1) {
            return nums2[index2 + k - 1]; // 因为是计算的length，所以对应数组下标进行-1
        }
        if (index2 == length2) {
            return nums1[index1 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[index1], nums2[index2]);
        }

        // 正常情况
        int half = k / 2;
        int newIndex1 = Math.min(index1 + half, length1) - 1;//  k/2 - 1
        int newIndex2 = Math.min(index2 + half, length2) - 1;
        int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]; // 比较 k/2 - 1
        if (pivot1 <= pivot2) {
            k -= (newIndex1 - index1 + 1); // k = k - k/2
            index1 = newIndex1 + 1;//
        } else {
            k -= (newIndex2 - index2 + 1); // k = k - k/2
            index2 = newIndex2 + 1; // 排除不可能的索引
        }
    }
}

测试用例：

@Test
public void isfindMedianSortedArrays() {
    int[] nums1 = {1,2};
    int[] nums2 = {1, 2, 3,4, 4, 5, 6, 7, 8, 9, 10}; // 
    double i = findMedianSortedArrays(nums1, nums2);
    Assert.assertNotNull(i);
}

小結

这道题主要是考查了二分法的使用，做这道题需要注意各种情况以及边界的处理，这道题也可以通过递归的方式去实现，出口和本题一致。

热门推荐：

• 【今日leecode】两数相加

• 万字图文浅析 ：ThreadPoolExecutor线程池

• 万字解析：最近服务准备上线，统一对微服务增加JVM参数

• 万文长字分析：想进大厂，你不得不掌握的CPU缓存基础

文末福利，最近整理一份面试资料《Java面试通关手册》，覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。获取方式：GitHub github.com/Tingyu-Notes，更多内容关注我的简书，陆续奉上。