algorithm - 使用 O(log n) 查询从 n 个条目的数据库中提取中值

Question

假设我有两个数据库，每个数据库都包含 n 条目。将中值定义为 n 的最小值。我们可以通过查询一次从给定的数据库中提取一个值。

Query(k) 返回指定数据库的第 k 个最小值。如何最多使用 O(log n) 查询找到中位数？

Answer 1

所需时间复杂度为O(log n)这表明我们应该尝试找到一种二进制搜索方法。与二分查找类似但略有不同，我们仍然划分n每次分成两半。

// As Query(k) will return k'th smallest element, considering database as container of sorted entries for understanding purpose. 
E.g., DB1 = [1, 3, 5, 7, 9]  DB2 = [2, 4, 6, 8, 10]. n = 5.

i = n / 2 = 2;
j = n - i = 3;

        i 
DB1 [1, 3, 5, 7, 9]

          j
DB2[2, 4, 6, 8, 10]

如果DB1.Query(i) < DB2.Query(j) , 这意味着来自 1 的元素至 i包括 DB1必须存在于第一个 n元素。

下一步是寻找 (n - i) n / 2 中的第 th(等于 DB1)元素(从 i + 1 到 n )和 DB2 (从 1 到 n )。这个过程可以看作是“切割”n / 2来自一个数据库的元素，并继续寻找另一个 n / 2 th 元素来自其他数据库和剪切后的"new"数据库。

如果DB1.Query(i) > DB2.Query(j) ，应用相同的程序，但我们“剪切”了 DB2数据库。

这样，我们每次都“切”n / 2来自其中一个数据库的元素，下一次是切割 (n / 2) / 2该数据库中的元素，直到:

• n = 1 ，较小的来自DB1.Query(1)和 DB2.Query(1)是“第n个元素”。
• 其中一个数据库结束了。然后只返回当前的 n来自另一个数据库的第 th 个元素。

这里我假设 DB1和 DB2是两个数据库的数据库处理程序。此语法类似于 C++，但您可以理解。这确保了 O(log n)复杂性。

// Find k'th smallest element of the two combind database entries
int findMedianofDatabaseHelper(DBHandler* db1, int i, DBHandler* db2, int j, const int n, int k) {
    if((n - i) > (n - j))
    {
        return findMedianofDatabaseHelper(db2, j, db1, i, n, k);
    }
    if(i >= n)
    {
        return db2->Query(j + k);
    }
    if(j >= n)
    {
        return db1->Query(i + k);
    }
    if(k == 1)
    {
        return min(db1->Query(i + 1), db2->Query(j + 1));
    }

    int aMid = min(k / 2, n - i);
    int bMid = k - aMid;

    if(db1->Query(i + aMid) <= db2->Query(j + bMid))
    {
        return findMedianofDatabaseHelper(db1, i + aMid, db2, j, n, k - aMid);
    }

    return findMedianofDatabaseHelper(db1, i, db2, j + bMid, n, k - bMid);
}

// assuming DBHandler is a wrapper of database handler/instance on which we can perform query
int findMedianofDatabase(DBHandler* db1, DBHandler* db2, int n)
{
    return findMedianofDatabaseHelper(db1, 0, db2, 0, n, n);
}

Here我用 C++ 模拟了工作程序。