哈，再介绍个操蛋的问题。当然，网上有很多解答，但是能让你完全看懂的不多，即便它的结果是正确的，可是解释上也是有问题的。
所以，为了以示正听，我也做了分析和demo，只要你愿意学习，你就一定能学会，并且不会有疑惑了。
可以侧面反映我的分析和算法都是逻辑严格，阐述清晰了。
————————————————————————————————————————————
原问题出于leetcode
Leetcode当然又是来源于实践了：对于两个有序的数组（升序），设A[]，长度m, B[]，长度为n, 如何找到第K小的数（此处根据中文语境做了处理，大多数资料都是照搬英文字面含义称为第K大数），当K为（m+n）/2时，结果就是上中位数。
我想在实际的应用领域中，估计会有这种需求出现，用最简单的两有序数组合并，然后自然得出需要的结果，时间复杂度接近于O(m+n)。而这个问题是存在O(log(m+n))时间复杂度的解决方案的，对于log级别的算法一定是二分查找，这里二分的类别就应该是有序的区间端。
解：第K小数
A，B两个数组，A的长度小于B，分别为m, n。如果m==0，则B[k-1]即为所求。1==K时，A[0]与B[0]中较小的那个即为所求。其它情况分析如下，取A数组的前num1个元素的子数组A1，再取B数组的前K-num1个元素的子数组B。我们设A1长度l1, B!长度l2。如果，B[l2-1]==A[l1-1]，A1和B1升序合并后应该改是…C[K-2],C[K-1]，其中C[k-2]==C[k-1]，值是A[l1-1]于B[l2-1]的其中之一，由于l1+l2==K，故而，我们找到了两个数组的第K小数就是C[K-1]，也即是A[l1-1]或者B[l2-1]；还剩下两种情况待分析，我们分别列出：
① A[l1-1]>B[l2-1]
此时，B可以分成两个子数组B[0…l2-1], B[l2...n-1]。这时候有一个关键问题需要理解，那就是B[0…l2-1]一定在第K小数序列之内， 因为如果A[l1-1]就是第K小数的话，B[0…l2-1]的l2个元素一定在它之前，所以B[0…l2-1]中不存在第K小数，第K小数只能在B[l2…n-1]中，或者在A[0…l1-1]中出现，因为我们已经有l2个K小数之前的元素，只要在上两个数组中取出l1的小数，就可知道l2+l1=K, 也就是第A，B数组的第K小数求出。当然，A[0…l1-1]，B]l2…n-1]中的l1小数的求解也是一样的过程，这样就可以递归算法实现了。
② A[l1-1]<B[l2-1]
与上一种情况是互补的，所以很容易分析出。
算法
//array2k.c
#include <stdio.h>
#include <stdlib.h>
#include <error.h>
#include <string.h>
int find2k(int array1[], int len1, int array2[], int len2, int k)
{
if (k<0)
{
fprintf(stderr, "k value is no ligal\n");
return -1;
}
// make sure len1<=len2
if (len1>len2)
{
return find2k(array2, len2, array1, len1, k);
}
// return condition
if (0==len1)
{
return array2[k-1];
}
if (1==k)
{
return array1[0]>=array2[0]?array2[0]:array1[0];
}
// num1+num2==k
int num1 = len1>=k/2?k/2:len1;
int num2 = k-num1;
if (array1[num1-1]==array2[num2-1])
{
return array1[num1-1];
}
else if (array1[num1-1]>array2[num2-1])
{
return find2k(array1, num1, &array2[num2], len2-num2, k-num2);
}
else
{
return find2k(&array1[num1], len1-num1, array2, num2, k-num1);
}
}
//test.c
#include "array2k.h"
#include <stdio.h>
#include <stdlib.h>
#include <error.h>
#include <string.h>
void main()
{
int array1[11] = {10,21,22,35,47,56,67};
int array2[11] = {33,44,55,63,72,83};
// 7==k
int ret = find2k(array1, 7, array2, 6, 7);
printf("7==k, %d\n", ret);
//k==(7+6)/2, mid number
ret = find2k(array1, 7, array2, 6, 6);
printf("6==k(mid number), %d\n", ret);
}
//result:
# ./test
7==k, 47
6==k(mid number), 44
Finally:
这两个问题是普遍和特性问题，应该是上中位问题是是第K小数问题的特例，而不是网上有些人说的用特列之上中位来求第K小数，哪里的分析我也看了，云里雾里得，因为它的前提就错了。
有序数组的最低时间复杂度的排序和查找问题，应该是实际工程中比较重要的算法需求，所以，这个问题还是请重视一下。