题目

给定两个有序列表，大小分别为m和n。给出一个算法，以O（logn+logm）时间找出两个列表合并后的有序列表中第k小元素

算法思想

设两个数组为A[1...m],B[1...n]，则中间位置分别为m/2与n/2，假设A[m/2]>B[n/2]，那么A[m/2...m]在A+B的n/2+m/2之后，此时，若k<n/2+m/2，那么就可以排除A[m/2...m]的元素，在剩余元素再进行上述操作，若k>n/2+m/2，那么就可以排除B[1...n/2]的元素，再剩余元素中寻找第k-n/2小项。

代码：

#include <iostream>
#define MAXLEN 100
using namespace std;
int Search(int A[],int B[],int aLeft, int aRight, int bLeft, int bRight, int k)
{
    int aMiddle = (aLeft + aRight) / 2;
    int bMiddle = (bLeft + bRight) / 2;
    if (aLeft > aRight)
        return B[bLeft + k - 1];
    if (bLeft > bRight)
        return A[aLeft + k - 1];
    if (A[aMiddle] > B[bMiddle])
    {
        if (k <= (aMiddle - aLeft) + (bMiddle - bLeft) + 2)
            return Search(A, B, aLeft, aMiddle - 1, bLeft, bRight, k);
        else
            return Search(A, B,aLeft, aRight, bMiddle + 1, bRight, k - (bMiddle - bLeft) - 1);
    }
    else
    {
        if (k <= (aMiddle - aLeft) + (bMiddle - bLeft) + 2)
            return Search(A, B, aLeft, aRight, bLeft, bMiddle - 1, k);
        else
            return Search(A, B, aMiddle + 1, aRight, bLeft, bRight, k - (aMiddle - aLeft) - 1);
    }
}
int main(void)
{
    int alen, blen,k;
    int A[MAXLEN],B[MAXLEN];
    cin >> alen;
    for (int i = 0; i < alen; i++)
    {
        cin >> A[i];
    }
    cin >> blen;
    for (int i = 0; i < blen; i++)
    {
        cin >> B[i];
    }
    cin >> k;
    cout << "第" << k << "小元素是" << Search(A, B, 0, alen - 1, 0, blen - 1, k) << endl;
    system("pause");
    return 0;
}