O（log n）クエリを使用してnエントリのデータベースからメディアンを抽出する

Question

それぞれがnのエントリを含む2つのデータベースを持っているとします。中央値をnの最小値に設定します。与えられたデータベースからクエリを使って、一度に1つの値を抽出することができます。

Query(k)は、指定されたデータベースのk番目の最小値を返します。最大でO(log n)個のクエリを使用して中央値を見つけるにはどうすればよいですか？

Answer 1

必要な時間の複雑さはO(log n)です。これは、バイナリ検索の方法を見つけようとしていることを示しています。バイナリ検索と同様ですが、バイナリ検索とはわずかに異なりますが、毎回nを2つの半分に分割します。 DB1の1iに含めからの要素が最初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)場合、。

次のステップは、今(n - i)番目（1からnまで）（n/2に等しい）（i + 1からnに）DB1の要素とDB2を見つけることになります。この手順は、1つのデータベースから「切断」n/2要素と見なすことができ、他のデータベースから他のn/2番目の要素を検索し、切断後に「新しい」データベースを検索し続けます。

DB1.Query(i) > DB2.Query(j)の場合、同じ手順が適用されますが、DB2データベースを "切り捨て"ます。 、

• n = 1DB1.Query(1)から小さい1：このように

  、我々はデータベースのいずれかからn/2の要素を「カット」しているたびに、次回はするまで、そのデータベースから(n/2)/2要素をカットすることですDB2.Query(1)は「n番目の要素」です。

• データベースの1つが終了します。次に、現在のn番目の要素を他のデータベースから戻します。

DB1とDB2は、2つのデータベースのデータベースハンドラです。この構文は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++で作業プログラムをシミュレートしました。

Answer 2

2つのデータベースののうち、最も小さい要素のn/2を照会すると、バイナリ検索（nが2の累乗でない場合、多少の調整が必要）があります。彼らが等しいなら、あなたの中央値があります。 m1<m2の場合は、最初は3n/4、次に小さい場合は1/4となります。逆の場合はm1>m2となります。繰り返す。

各ステップでは、上記の選択した要素と同じ数の下にある要素があります。