LeetCode第四题：寻找两个正序数组的中位数

题目来源：LeetCode第四题

1.题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]

输出：2.00000

解释：合并数组 = [1,2,3] ，中位数 2

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

2.解题思路

解法一：合并两个数组后直接查找

• 描述：很容易想到的解法就是直接将两个数组按照排序合并，合并如果长度是奇数，中位数就是数组中间元素，偶数的话，中位数就是中间两个元素的平均值。
• 时间复杂度：O(m+n)。我们需要遍历两个数组的所有元素，将他们放到新的数组里面。
• 空间复杂度：O(m+n)。我们新建了一个长度为m+n的数组来存储两个数组的所有元素。
• 参考代码：

java版：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] merged = new int[m + n];

        int i = 0, j = 0, k = 0;
        // 合并两个已排序数组
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        while (i < m) {
            merged[k++] = nums1[i++];
        }
        while (j < n) {
            merged[k++] = nums2[j++];
        }
        // 根据奇偶找到中位数
        if ((m + n) % 2 == 1) {
            return (merged[(m + n) / 2]);
        } else {
            return (merged[(m + n) / 2 - 1] + merged[(m + n) / 2]) / 2.0;
        }
    }
}

C++版：

class Solution
{
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
	{
		int m = nums1.size();
		int n = nums2.size();

		vector<int> merged(m + n);

		int i = 0, j = 0, k = 0;
		//合并两个已排序的数组
		while (i < m && j < n)
		{
			if (nums1[i] < nums2[j])
			{
				merged[k++] = nums1[i++];
			}
			else
			{
				merged[k++] = nums2[j++];
			}
		}
		while (i < m)
		{
			merged[k++] = nums1[i++];
		}
		while (j < n)
		{
			merged[k++] = nums2[j++];
		}

		//找到中位数
		if ((m + n) % 2 == 1)
		{
			return merged[(m + n) / 2];
		}
		else
		{
			return (merged[(m + n) / 2 - 1] + merged[(m + n) / 2]) / 2.0;
		}
	}
};

C版：

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	int m = nums1Size;
	int n = nums2Size;

	// 使用动态内存分配来创建合并后的数组
	int* merged = (int*)malloc((m + n) * sizeof(int));

	int i = 0, j = 0, k = 0;

	// 合并两个已排序数组
	while (i < m && j < n) {
		if (nums1[i] < nums2[j]) {
			merged[k++] = nums1[i++];
		}
		else {
			merged[k++] = nums2[j++];
		}
	}
	while (i < m) {
		merged[k++] = nums1[i++];
	}
	while (j < n) {
		merged[k++] = nums2[j++];
	}

	double result;
	// 找到中位数
	if ((m + n) % 2 == 1) {
		result = (double)merged[(m + n) / 2];
	}
	else {
		result = (merged[(m + n) / 2 - 1] + merged[(m + n) / 2]) / 2.0;
	}

	// 释放动态分配的内存
	free(merged);

	return result;
}

解法二：插入法

• 描述：我们的目标只是找到中位数，并不需要真的去合并数组，我们可以用两个指针来模拟合并过程，两个指针分别指向两个数组的起始位置，在用一个数来模拟合并后数组的索引，当索引到达中位数的位置时吗，我们就可以判断奇偶来得到答案。
• 时间复杂度：O(m+n)。我们最多需要遍历(m+n)/2+1个元素，当m和n足够大时，可以认为是O(m+n)。
• 空间复杂度：O(1)。我们并没有使用任何与输入大小成比例的额外空间，只是用了几个辅助变量。
• 参考代码：

java版：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        int i = 0, j = 0;
        // 这两个是用来暂存合并后的数组中心元素，因为分为奇偶情况，需要两个
        int mid1 = 0, mid2 = 0;

        for (int k = 0; k <= (m + n) / 2; k++) {
            // 用mid1来存储相对较小的那个值
            mid1 = mid2;
            // i<m来确保nums1不越界，j>=n来检查nums2是否越界，越界后说明已经遍历完了nums2数组
            // nums1[i] < nums2[j]，比较当前nums1和nums2的指针位置元素，如果nums1较小，则从nums1取元素
            // 否则的话从nums2中取元素
            if (i < m && (j >= n || nums1[i] < nums2[j])) {
                mid2 = nums1[i++];
            } else {
                mid2 = nums2[j++];
            }
        }

        // 如果为偶数，就取mid1和mid2的平均数，否则取mid2
        if ((m + n) % 2 == 0) {
            return (mid1 + mid2) / 2.0;
        } else {
            return mid2;
        }
    }
}

C++版：

class Solution
{
public:

	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
	{
		int m = nums1.size();
		int n = nums2.size();

		// 这两个是用来暂存合并后的数组中心元素，因为分为奇偶情况，需要两个
		int mid1 = 0, mid2 = 0;

		int i = 0, j = 0;

		for (int k = 0; k <= (m + n) / 2; k++)
		{
			// 用mid1来存储相对较小的那个值
			mid1 = mid2;
			// i<m来确保nums1不越界，j>=n来检查nums2是否越界，越界后说明已经遍历完了nums2数组
			// nums1[i] < nums2[j]，比较当前nums1和nums2的指针位置元素，如果nums1较小，则从nums1取元素
			// 否则的话从nums2中取元素
			if (i < m && (j >= n || nums1[i] < nums2[j]))
			{
				mid2 = nums1[i++];
			}
			else
			{
				mid2 = nums2[j++];
			}
		}

		// 如果为偶数，就取mid1和mid2的平均数，否则取mid2
		if ((m + n) % 2 == 0)
		{
			return (mid1 + mid2) / 2.0;
		}
		else
		{
			return mid2;
		}
	}
};

C版：

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
	int m = nums1Size;
	int n = nums2Size;

	int mid1 = 0, mid2 = 0;
	int i = 0, j = 0;

	// 使用插入法，只需要遍历到中位数的位置
	for (int k = 0; k <= (m + n) / 2; k++)
	{
		mid1 = mid2;
		if (i < m && (j >= n || nums1[i] < nums2[j]))
		{
			mid2 = nums1[i++];
		}
		else
		{
			mid2 = nums2[j++];
		}
	}
	// 如果 m + n 是偶数，那么中位数是两个中间值的平均
	// 如果是奇数，那么中位数是第二个中间值
	if ((m + n) % 2 == 0)
	{
		return (mid1 + mid2) / 2.0;
	}
	else
	{
		return mid2;
	}
}

解法三：递归法

• 描述：这个方法的核心就是找到两个数组中第k小的数，无论k是多少，我们每次都可以排除掉一部分不可能是第k小的数，那么问题的规模就会越来越小，直到得到答案。这题我们可以取两个数组中的第k/2个元素进行比较，如果nums1的第k/2小的元素小于nums2的第k/2小的元素，那就说明nums1的这k/2个元素都不可能是整体的第k小的元素（因为它们都小于nums2的k/2个元素），所以我们可以排除掉它们。反之，我们可以排除num2中k/2个元素。按照这个方法，一直递归进行下去，直到k=1或者其中一个数组为空。k=1就返回两个指针小的那一个，或者有一个数组为空，只需要返回另一个数组第k小的元素。
• 时间复杂度：每进行一次循环，我们就减少 k / 2 个元素，所以时间复杂度是 O（log（k）），而 k = （m + n）/ 2 ，所以最终的复杂也就是 O（log（m + n））。
• 空间复杂度：O(1)。我们只需要常数的额外空间来存储变量。
• 参考代码：

java版：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int total = nums1.length + nums2.length;

        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小的数
    // nums1是第一个数组 i 是第一个数组的起始索引
    // nums2是第二个数组 j 是第二个数组的起始索引
    // k 是我们需要的第k小的数，k值会因为递归越来越小。
    private double findKth(int[] nums1, int i, int[] nums2, int j, int k) {

        // 这是为了让nums1是较短的那个数组，这样nums1为空的话，我们就只需查找nums2了
        // 记得不是直接判断长度，是判断数组剩余的长度
        // 还有交换记得把i j也要换
        if (nums1.length - i > nums2.length - j) {
            return findKth(nums2, j, nums1, i, k);
        }

        // 如果numns1为空了，判断条件是nums1的长度等于起始索引
        // 如果起始索引都等于长度了，说明nums1里面的元素都被排除了
        // 我们就只需要返回nums2中第k小的元素就行
        if (nums1.length == i) {
            return nums2[j + k - 1];
        }

        // 如果k为1，说明我们找到了排除完后的第一小元素，也就是我们需要的元素
        // 这个时候我们就返回两个数组中的较小值就行
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }

        // si是帮我们确定nums1中的参与比较的数的索引，当然要看索引有没有超过nums1的大小，最多只能等于
        // 例如 1 3 5 7
        // 和 2 4 6 8 10
        // 总数为9是奇数 也就是我们需要找到第k/2+1小的元素，也就是第5小的元素
        // 我们比较两个数组中第5/2小的元素，也就是3和4
        // 4大，说明1 3都不可能是第5小的元素，直接排除，在剩下的数里面找第3小的元素
        // 继续3/2 ，比较两个数组的第1小的元素，排除了1 3后就是5，比2大，所以2不可能是第3小的元素
        // 然后找第2小的元素，2/2，还是比较第1小的元素，5比4大，4不是第2小的元素，排除
        // 最后k=1了，现在的数组是 5 7 在这个数组中找第一小的元素，就是比较5 和 6 ，得出结果
        // ----------------------6 8 10
        int si = Math.min(nums1.length, i + k / 2);

        // si已经拿出了k / 2个数，sj这边就只需要在拿k-k/2个数就行
        // 因为我们是在两个数组中找第k小的数
        int sj = j + k - k / 2;

        // 如果nums1中剩余数的第k/2小的数比nums2中剩余数的第k/2小的数大
        // 说明nums2中前sj-j个元素不可能是第k小的元素，在剩下的数里面继续寻找第k - (sj - j)小的数
        if (nums1[si - 1] > nums2[sj - 1]) {
            return findKth(nums1, i, nums2, sj, k - (sj - j));
        } else {
            return findKth(nums1, si, nums2, j, k - (si - i));
        }

    }
}

C++版：

class Solution
{
public:

	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
	{
		int total = nums1.size() + nums2.size();

		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);
		}
	}

private:
	// 用递归的方法找到两个数组合并后的第k小的数
	// nums1是第一个数组 i 是第一个数组的起始索引
	// nums2是第二个数组 j 是第二个数组的起始索引
	// k 是我们需要的第k小的数，k值会因为递归越来越小。
	double findKth(vector<int>& nums1, int i, vector<int>& nums2, int j, int k)
	{
		// 这是为了让nums1是较短的那个数组，这样nums1为空的话，我们就只需查找nums2了
		// 记得不是直接判断长度，是判断数组剩余的长度
		// 还有交换记得把i j也要换
		if (nums1.size() - i > nums2.size() - j)
		{
			return findKth(nums2, j, nums1, i, k);
		}
		// 如果numns1为空了，判断条件是nums1的长度等于起始索引
	   // 如果起始索引都等于长度了，说明nums1里面的元素都被排除了
	   // 我们就只需要返回nums2中第k小的元素就行
		if (nums1.size() == i)
		{
			return nums2[j + k - 1];
		}
		// 如果k为1，说明我们找到了排除完后的第一小元素，也就是我们需要的元素
		// 这个时候我们就返回两个数组中的较小值就行
		if (k == 1)
		{
			return min(nums1[i], nums2[j]);
		}
		// si是帮我们确定nums1中的参与比较的数的索引，当然要看索引有没有超过nums1的大小，最多只能等于
		// 例如 1 3 5 7
		// 和 2 4 6 8 10
		// 总数为9是奇数 也就是我们需要找到第k/2+1小的元素，也就是第5小的元素
		// 我们比较两个数组中第5/2小的元素，也就是3和4
		// 4大，说明1 3都不可能是第5小的元素，直接排除，在剩下的数里面找第3小的元素
		// 继续3/2 ，比较两个数组的第1小的元素，排除了1 3后就是5，比2大，所以2不可能是第3小的元素
		// 然后找第2小的元素，2/2，还是比较第1小的元素，5比4大，4不是第2小的元素，排除
		// 最后k=1了，现在的数组是 5 7 在这个数组中找第一小的元素，就是比较5 和 6 ，得出结果
		// ----------------------6 8 10
		int si = min((int)nums1.size(), i + k / 2);
		// si已经拿出了k / 2个数，sj这边就只需要在拿k-k/2个数就行
		// 因为我们是在两个数组中找第k小的数
		int sj = j + k - k / 2;

		// 如果nums1中剩余数的第k/2小的数比nums2中剩余数的第k/2小的数大
		// 说明nums2中前sj-j个元素不可能是第k小的元素，在剩下的数里面继续寻找第k - (sj - j)小的数
		if (nums1[si - 1] > nums2[sj - 1])
		{
			return findKth(nums1, i, nums2, sj, k - (sj - j));
		}
		else
		{
			return findKth(nums1, si, nums2, j, k - (si - i));
		}
	}
};

C版：

double findKth(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
	// 确保nums1是较短的数组
	if (nums1Size > nums2Size) {
		return findKth(nums2, nums2Size, nums1, nums1Size, k);
	}
	if (nums1Size == 0) {
		return nums2[k - 1];
	}
	if (k == 1) {
		return nums1[0] < nums2[0] ? nums1[0] : nums2[0];
	}

	// 分割k
	int i = nums1Size < k / 2 ? nums1Size : k / 2;
	int j = k - i;

	// 通过比较nums1和nums2中的元素来排除部分数字
	if (nums1[i - 1] < nums2[j - 1]) {
		return findKth(nums1 + i, nums1Size - i, nums2, nums2Size, k - i);
	}
	else {
		return findKth(nums1, nums1Size, nums2 + j, nums2Size - j, k - j);
	}
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	int total = nums1Size + nums2Size;
	if (total % 2 == 0) {
		return (findKth(nums1, nums1Size, nums2, nums2Size, total / 2) +
			findKth(nums1, nums1Size, nums2, nums2Size, total / 2 + 1)) / 2.0;
	}
	else {
		return findKth(nums1, nums1Size, nums2, nums2Size, total / 2 + 1);
	}
}

解法四：二分查找法

• 描述：我们要想找到两个数组的中位数，可以找到两个数组中正好位于中位数前面的数，那么问题就是找到max(nums1[i-1], nums2[j-1])和min(nums1[i], nums2[j])（其中i和j是我们选取的分割点）。由于其中一个数组始终较短，我们可以在较短的数组上执行二分查找来找到一个适当的i，这样就可以确定第二个数组的j位置。
• 时间复杂度：我们对较短的数组进行了二分查找，所以时间复杂度是 O(log(min(m，n)))。
• 空间复杂度：只有一些固定的变量，和数组长度无关，所以空间复杂度是 O (1) 。
• 参考代码：

java版：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 确保我们只在长度较短的数组上进行二分查找，所以需要保证nums1比nums2短
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;

        // 两个数组长度之和的一半（如果是奇数的话，+1确保左侧的元素总是大于等于右侧的元素）
        int halfLen = (m + n + 1) / 2;

        // 这个表示分割点，用来限制搜索范围，iMin表示nums1可以考虑的最小切割位置
        // iMax表示nums1最大的切割位置
        int iMin = 0, iMax = m;

        while (iMin <= iMax) {
            // i是nums1的分割位置，初始化为nums1中间
            int i = (iMin + iMax) / 2;
            // j是nums2的分割位置，因为找中位数，所以是长度一半-nums1分割的地方
            // 保证i j加起来是到中位数
            int j = halfLen - i;

            // 如果i<m 并且nums2分割线的左侧元素都比nums1分割线的右侧元素大，说明i小了
            // 1 | 3 9 左边下面分割线的左边10都比上面分割线的右边3大，所以i需要右移
            // 7 8 | 10
            // 1 3 | 9 i右移一次，这样就满足了条件
            // 7 | 8 10
            if (i < m && nums2[j - 1] > nums1[i]) {
                iMin = i + 1;
                // 如果i>0,并且nums1分割线的左侧元素比nums2的分割线的右侧元素大，说明i大了
                // 14 | 15 18 左边nums1分割线左边的元素都比nums2右边的元素大了，所以i需要左移
                // 7 9 10 | 13 19
                // | 14 15 18 i左移一次，这样就是正确的位置
                // 7 9 10 13 | 19
            } else if (i > 0 && nums1[i - 1] > nums2[j]) {
                iMax = i - 1;
            } else {
                // 如果i已经在正确的位置
                // 设置整个分割线左侧的最大值为maxLeft
                int maxLeft;
                // 如果i=0，说明nums1的分割线在nums1最左边，这时的左侧最大值就是nums2的分割线的左边的值
                if (i == 0)
                    maxLeft = nums2[j - 1];
                // 如果j=0，说明nums2的分割线在最左边，这时的左侧最大值就是在num1分割线的左边的值
                else if (j == 0)
                    maxLeft = nums1[i - 1];
                else
                    // 否则，分割线左侧的最大值是nums1分割线左边和nums2分割线左边的较大值
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                // 如果m+n是奇数，那么结果只有一个，根据分割大方法，左侧元素个数大于等于右侧
                // 所以结果就是分割线左侧元素的最大值
                if ((m + n) % 2 == 1)
                    return maxLeft;

                // 分割线右侧元素的最小值设置为minRight
                int minRight;
                // 如果nums1的分割线在最右边，说明nums1右侧没有值了
                // 那么整个右侧的最小值就是nums2的分割线右侧的值
                if (i == m)
                    minRight = nums2[j];
                // 如果nums2的分割线在最右边，说明nums2的右侧没有值了
                // 那么整个右侧的最小值就是nums1的分割线右侧的值
                else if (j == n)
                    minRight = nums1[i];
                else
                    // 否则整个右侧的最小值就是nums1分割线右边和nums2分割线右边较小值
                    minRight = Math.min(nums1[i], nums2[j]);
                // 到这里说明是偶数，中位数是分割线左边最大值和右边最小值的平均数
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}

C++版：

class Solution
{
public:
		double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
	// 确保我们只在长度较短的数组上进行二分查找，所以需要保证nums1比nums2短
	if (nums1.size() > nums2.size())
	{
		return findMedianSortedArrays(nums2, nums1);
	}

	int m = nums1.size();
	int n = nums2.size();
	// 两个数组长度之和的一半（如果是奇数的话，+1确保左侧的元素总是大于等于右侧的元素）
	int halfLen = (m + n + 1) / 2;

	// 这个表示分割点，用来限制搜索范围，iMin表示nums1可以考虑的最小切割位置
	// iMax表示nums1最大的切割位置
	int iMin = 0, iMax = m;

	while (iMin <= iMax)
	{
		// i是nums1的分割位置，初始化为nums1中间
		int i = (iMax + iMin) / 2;
		// j是nums2的分割位置，因为找中位数，所以是长度一半-nums1分割的地方
	   // 保证i j加起来是到中位数
		int j = halfLen - i;

		// 如果i<m 并且nums2分割线的左侧元素都比nums1分割线的右侧元素大，说明i小了
	   // 1 | 3 9 左边下面分割线的左边10都比上面分割线的右边3大，所以i需要右移
	   // 7 8 | 10
	   // 1 3 | 9 i右移一次，这样就满足了条件
	   // 7 | 8 10
		if (i < m && nums1[i] < nums2[j - 1])
		{
			iMin = i + 1;
		}
		// 如果i>0,并且nums1分割线的左侧元素比nums2的分割线的右侧元素大，说明i大了
			// 14 | 15 18 左边nums1分割线左边的元素都比nums2右边的元素大了，所以i需要左移
			// 7 9 10 | 13 19
			// | 14 15 18 i左移一次，这样就是正确的位置
			// 7 9 10 13 | 19
		else if (i > 0 && nums1[i - 1] > nums2[j])
		{
			iMax = i - 1;
		}
		else
		{
			// 如果i已经在正确的位置
			// 设置整个分割线左侧的最大值为maxLeft
			int maxLeft = 0;
			// 如果i=0，说明nums1的分割线在nums1最左边，这时的左侧最大值就是nums2的分割线的左边的值
			if (i == 0)
			{
				maxLeft = nums2[j - 1];
			}
			// 如果j=0，说明nums2的分割线在最左边，这时的左侧最大值就是在num1分割线的左边的值
			else if (j == 0)
			{
				maxLeft = nums1[i - 1];
			}
			else
			{
				// 否则，分割线左侧的最大值是nums1分割线左边和nums2分割线左边的较大值
				maxLeft = max(nums1[i - 1], nums2[j - 1]);
			}
			// 如果m+n是奇数，那么结果只有一个，根据分割大方法，左侧元素个数大于等于右侧
			// 所以结果就是分割线左侧元素的最大值
			if ((m + n) % 2 == 1)
			{
				return maxLeft;
			}
			// 分割线右侧元素的最小值设置为minRight
			int minRight = 0;
			// 如果nums1的分割线在最右边，说明nums1右侧没有值了
			// 那么整个右侧的最小值就是nums2的分割线右侧的值
			if (i == m)
			{
				minRight = nums2[j];
			}
			// 如果nums2的分割线在最右边，说明nums2的右侧没有值了
		   // 那么整个右侧的最小值就是nums1的分割线右侧的值
			else if (j == n)
			{
				minRight = nums1[i];
			}
			else
			{
				// 否则整个右侧的最小值就是nums1分割线右边和nums2分割线右边较小值
				minRight = min(nums1[i], nums2[j]);
			}
			// 到这里说明是偶数，中位数是分割线左边最大值和右边最小值的平均数
			return (maxLeft + minRight) / 2.0;
		}
	}
	return 0.0;
}
};

C版：

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	if (nums1Size > nums2Size) {
		// 交换数组，以确保nums1是更短的数组
		return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
	}

	int m = nums1Size;
	int n = nums2Size;
	int halfLen = (m + n + 1) / 2; // 计算中位数位置
	int iMin = 0, iMax = m;

	while (iMin <= iMax) {
		int i = (iMin + iMax) / 2;
		int j = halfLen - i;

		if (i < m && nums1[i] < nums2[j - 1]) {
			// i 值偏小
			iMin = i + 1;
		}
		else if (i > 0 && nums1[i - 1] > nums2[j]) {
			// i 值偏大
			iMax = i - 1;
		}
		else {
			// i 是完美的
			int maxOfLeft;
			if (i == 0) maxOfLeft = nums2[j - 1];
			else if (j == 0) maxOfLeft = nums1[i - 1];
			else maxOfLeft = fmax(nums1[i - 1], nums2[j - 1]);

			if ((m + n) % 2 == 1) {
				return maxOfLeft;
			}

			int minOfRight;
			if (i == m) minOfRight = nums2[j];
			else if (j == n) minOfRight = nums1[i];
			else minOfRight = fmin(nums1[i], nums2[j]);

			return (maxOfLeft + minOfRight) / 2.0;
		}
	}
	return 0.0;
}