思路

logm+logn即可推断是分治，每次折半得到两个数组的A[midA]和B[midB]，有：

A[midA]>B[midB]时：
- 若midA+midB（实际上是midA+midB-beginA-beginB+2，下同）的元素个数>k，则midB之后的序列肯定不包含在最终的有序k个元素的数列中。不能包括=k的情况，因为=k时，midB也可能包含在最终的有序k个元素数列中。这里的等于号的逻辑错误看了很久才发现。
- 若midA+midB的元素个数<=(注意是小于等于)k，则midA及之前的元素肯定包含在最终的有序k个元素的数列中，k=k-(midA-beginA+1)，转换为一个更小的求第k个数的问题。

#include <iostream>
#define M 5
#define N 6
using namespace std;
int INDEX1[M] = { 1,2,4,5,6 };
int INDEX2[N] = { 2,3,5,7,9,10 };


int FindK(int*A, int*B, int beginA, int endA, int beginB, int endB, int k) {
    printf("A:%d-->%d B:%d-->%d\n", beginA, endA, beginB, endB);
    int midA = (beginA + endA) / 2;
    int midB = (beginB + endB) / 2;
    //已经确定了其中一个有序序列
    //剩下的有序序列取第k小的数即可
    if (beginA > endA ) {
        cout << "K:" << k << endl;
        return B[beginB + k - 1];
    }
    if (beginB > endB ) {
        cout << "K:" << k << endl;
        return A[beginA + k - 1];
    }
    //beginA、beginB是已确定的两个范围
    //len是从mid到begin的元素个数
    int len = midA - beginA + midB - beginB + 2;
    if (A[midA] < B[midB]) {
        if (len <= k){
            //因为折半后合并的元素个数小于K
            //midA之前的元素一定包含在最终求得第K小的数的有序数列中
            //但midB前的元素可能大于a[midA],无法确定
            return FindK(A, B, midA + 1, endA, beginB, endB, k - (midA - beginA + 1));
        }
        else
            //因为合并的元素个数大于所求K
            //midA后的元素可能小于midB，但midB后的元素肯定大于midB，不可能包含在最终的有序数列中
            return FindK(A, B, beginA, endA, beginB, midB - 1, k);
    }
    else{
        if (len <= k)
            return FindK(A, B, beginA, endA, midB + 1, endB, k - (midB - beginB + 1));
        else
            return FindK(A, B, beginA, midA - 1, beginB, endB, k);
    }

}

//实际这里的边界情况判断并不需要
int Find(int*A, int*B, int beginA, int endA, int beginB, int endB, int k) {
    if (B[0] >= A[M - 1]) {
        //cout << "B[0] >= A[M]";
        if (k <= M)
            return A[k - 1];
        return B[k - M - 1];
    }
    if (A[0] >= B[N - 1]) {
        //cout << "A[0] >= B[N]";
        if (k <= N)
            return B[k - 1];
        return A[k - N - 1];
    }
    if (k <= M && B[0] >= A[k - 1])
        return A[k - 1];
    if (k <= N && A[0] >= B[k - 1])
        return B[k - 1];
    return FindK(A, B, beginA, endA, beginB, endB, k);
}

void showArray(int a[], int length)
{
    for (int i = 0; i < length; i++)
    {
        cout << a[i] << " ";
    }
    cout << "\n";
}

int main(void) {
    cout << "INDEX1：";
    showArray(INDEX1, M);
    cout << "INDEX2：";
    showArray(INDEX2, N);
    int k;
    cin >> k;
    cout << "第" << k << "小的数是:" << Find(INDEX1, INDEX2, 0, M - 1, 0, N - 1, k);
    system("pause");
    return 0;
}