fork(2) download 
  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5. #define N 5
  6.  
  7. struct DBHandler {
  8.     int* arr;
  9.     DBHandler() {}
  10.     DBHandler(int* pArr) {
  11.         arr = pArr;
  12.     }
  13.     int Query(int k) {
  14.         return arr[k - 1];
  15.     }
  16. };
  17.  
  18. // Find k'th smallest element of the two combind database entries
  19. int findMedianofDatabaseHelper(DBHandler* db1, int i, DBHandler* db2, int j, const int n, int k) {
  20.     if((n - i) > (n - j))
  21.     {
  22.         return findMedianofDatabaseHelper(db2, j, db1, i, n, k);
  23.     }
  24.     if(i >= n)
  25.     {
  26.         return db2->Query(j + k);
  27.     }
  28.     if(j >= n)
  29.     {
  30.         return db1->Query(i + k);
  31.     }
  32.     if(k == 1)
  33.     {
  34.         return min(db1->Query(i + 1), db2->Query(j + 1));
  35.     }
  36.  
  37.     int aMid = min(k / 2, n - i);
  38.     int bMid = k - aMid;
  39.  
  40.     if(db1->Query(i + aMid) <= db2->Query(j + bMid))
  41.     {
  42.         return findMedianofDatabaseHelper(db1, i + aMid, db2, j, n, k - aMid);
  43.     }
  44.  
  45.     return findMedianofDatabaseHelper(db1, i, db2, j + bMid, n, k - bMid);
  46. }
  47.  
  48. // assuming DBHandler is a wrapper of database handler/instance on which we can perform query
  49. int findMedianofDatabase(DBHandler* db1, DBHandler* db2, int n)
  50. {
  51.     return findMedianofDatabaseHelper(db1, 0, db2, 0, n, n);
  52. }
  53.  
  54. int main() {
  55.     int arr1[N] = {11, 13, 15, 17, 19};
  56.     int arr2[N] = {12, 14, 16, 18, 20};
  57.     DBHandler * db1 = new DBHandler(arr1);
  58.     DBHandler * db2 = new DBHandler(arr2);
  59.     cout << findMedianofDatabase(db1, db2, N) << endl; // output = 15
  60.     delete db1;
  61.     delete db2;
  62.     return 0;
  63. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin 
Standard input is empty
stdout 
15
https://ideone.com/Jf9P94
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!