FindMedian, C++ (gcc)

FindMedian

/*Find Median in Large Integer File of Integers
Find the median from a large file of integers. You can not access the numbers by index, 
can only access it sequentially. And the numbers cannot fit in memory.
*/
#include<vector>
#include <iostream>
#include <limits.h>

using namespace std;

int find(vector<int>& v, int countTarget, long left, long right){ // the mid must ex
    //if(left>= right) return left; 
    int guess = (left+right)/2;
    int count = 0; 
    int res = left; // guessing the mid
    for(auto x: v){
        if(x <= guess) {
            count++;
            res = max(res,x); 
        }
    }
    if(count == countTarget) return res; // found countTarget number 
    if(count < countTarget){
        res = find(v, countTarget, max(res+1, guess), right); 
    }
    else{
        res = find(v, countTarget, left, res);
    }
    return res;
}

double findMid(vector<int>& v){
    int N = 0;
    for(auto x: v) N++;
    
    if(N%2) //odd 
       return find(v, N/2 + 1, INT_MIN, INT_MAX);
    else{
        int x = find(v, N/2 , INT_MIN, INT_MAX);
        int y = find(v, N/2 + 1, INT_MIN, INT_MAX);
        return (x+y)/2.0; 
    }
    
    return 0; 
}
int main()
{
     
    vector<int> v = {1,2,3}; 
    double m = findMid(v); 
    cout << "m(2.0) = " << m << endl;
    
    v = {1,2,3,4};
    cout << "m(2.5) = " << findMid(v) << endl;
  
  
    v = {1};
    cout << "m(1) = " << findMid(v) << endl;
  
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development