一、LeetCode 4. 寻找两个正序数组的中位数
题目介绍：
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例：
输入： nums1 = [1,3], nums2 = [2] 输出： 2.00000 解释： 合并数组 = [1,2,3] ，中位数 2
解题思路
从题目上来分析，有两个要求要满足：
- 要查找出两个数组
nums1和nums2的中位数
- 要满足算法的时间复杂度是 O(log(m+n))O(log(m+n))O(log(m+n))
我们逐一来看。
数组的中位数：即两个数组合并后，取数组最中间的一个（数组长度为奇数）或两个数（数组长度为偶数）的平均数。 并且已知数组nums1和nums2是正序（即由大到小）排列的。
那我们需要把两个数组进行从小到大的完全合并、排序，然后再查找、计算这个中位数吗？
其实并不需要，因为都是两个数组从小到大排列的，所以我们仅查找出符合要求的最中间一个或两个数。
我们可以设置一个数组nums，将所给数组nums1、nums2中的值按小到达放入，直到符合的长度。
这个数组nums所需的长度计算规则：
// 根据数组的长度以及是偶数还是奇数，我们可以计算出需要的 - 基数取最中间的一位，偶数取最中间的两位 const maxNumsLength = len % 2 === 0 ? len / 2 + 1 : Math.ceil(len / 2); // 加入输入的是 [1, 3] [2]，通过计算可得maxNumsLength值为2 // 则nums中需要存入 [1, 2]
我们来看下代码的实现：
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var findMedianSortedArrays = function(nums1, nums2) { // 获取两个数组的长度和 const len = nums1.length + nums2.length; // 根据数组的长度以及是偶数还是奇数，我们可以计算出需要的 - 基数取一位，偶数取两位 const maxNumsLength = len % 2 === 0 ? len / 2 + 1 : Math.ceil(len / 2); // 设置nums存储元素 const nums = []; // 每次取出各自数组中的最小值（即数组的首位子元素），进行比较，将元素放入到nums中，并且将原数组中的该元素移除。 // 每次存储nums1的首位 let nums1First = nums1.shift(); // 每次存储nums2的首位 let nums2First = nums2.shift(); // 该循环的条件为 nums.length < maxNumsLenth 并且nums1First 或者nums2First有值存在 while ( (nums1First !== undefined || nums2First !== undefined) && nums.length < maxNumsLength) { // 边界校验：当nums1First为undefined时，表示此时的nums1数组已经空了，只存储nums2的元素即可 if (nums1First === undefined) { nums.unshift(nums2First); nums2First = nums2.shift(); continue; } // 边界校验：当nums2First为undefined时，表示此时的nums2数组已经空了，只存储nums1的元素即可 if (nums2First === undefined) { nums.unshift(nums1First); nums1First = nums1.shift(); continue; } // 不为空时，比较二者大小，取最小值，放入数组nums中 if (nums1First > nums2First) { nums.unshift(nums2First); nums2First = nums2.shift(); } else { nums.unshift(nums1First); nums1First = nums1.shift(); } } // 中位数 let median; // 如果是偶数取前两个否则取第一个 if (len % 2 === 0) { median = (nums[1] + nums[0]) / 2; } else { median = nums[0]; } // 保留5位小数 return middle.toFixed(5) };
提交代码，我们看下执行情况，从执行用时来看，这个算法实现的还不错。
但是，这样的算法实现达到了题目要求的O(log(m+n))O(log(m+n))O(log(m+n))了吗？
其实并没有，看下现在的时间复杂度是 O((m+n)2+1)O(\tfrac{(m+n)}{2} + 1)O(2(m+n)+1)，即O(m+n)O(m+n)O(m+n)。
二、二分法查找
二分法查找，是指在一组有序数组查找某个指定元素的算法。
每次查找的开始都是数组的二分之一处开始，查看是否符合要求。如果不符合，则向上或者向下进行查找。
举例说明：在数组 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]中查找数字10的索引。
首先使用常规算法：枚举比对
const findKey = (nums, target) => { // 遍历nums的所有元素 for (let i = 0; i < nums.length; i++) { if (nums[i] === target){ return i; } } } // 调用函数 const index = findKey([1, 2, 3, 5, 6], 6); // 一共执行了6次比对 console.log(index); // 6
此种算法的时间复杂度是O(n)O(n)O(n)。
如果使用二分法查找呢？
二分法的一个前提条件就是数组必需是有序的，可以是正序也可以是逆序。
const halfFindKey = (nums, target) { // 声明一个起始位置索引 let startIndex = 0; let endIndex = nums.length - 1; let halfIndex; do { // 取二分之一处位置，考虑是偶数长度还是奇数长度 // 取二分之一位置 halfIndex = startIndex + Math.floor((endIndex - startIndex) / 2); // 当前值与target比对 if (target === nums[halfIndex]) { return halfIndex } else { // 比较二者大小 if (target > nums[halfIndex]) { // 说明target在右面 startIndex = halfIndex + 1; } else { endIndex = halfIndex - 1; } } // 考虑边界情况，说明只有一个元素了 if(startIndex === endIndex - 1) { // 判断是向上还是向下走 return halfIndex > startIndex ? startIndex : endIndex; } } while (halfIndex) } // 调用函数 const index = halfFindKey([1, 2, 3, 4, 5, 6], 6); // 执行3次循环，每次比对的元素分别是 nums[2]、nums[4]、nums[5] console.log(index); // 3
该算法的时间复杂度是 O(logn)O(logn)O(logn)，每次取数组的二分之一进行查询。
现在我们把目光再转移到这个 寻找两个正序数组的中位数问题上。
