Median of two sorted vectors

median-of-two-sorted-vectors.cc

// median of two sorted arrays

#include <iostream>
#include <vector>
#include <queue>

std::vector<int> merge(const std::vector<int>& v1, const std::vector<int>& v2){
  std::vector<int> result(v1.size()+v2.size());
  int i=0;
  int j=0;
  int k=0;

  //insert the lowest of the two arrays at each index
  while(i<v1.size() && j<v2.size()){
    result[k++] = (v1[i]<=v2[j]) ? v1[i++] : v2[j++];
  }

  //insert the rest of v1
  while(i<v1.size())
    result[k++] = v1[i++];

  //insert the rest of v2
  while(j<v2.size())
    result[k++] = v2[j++];
    
  return result;
}

double median(const std::vector<int>& v1, const std::vector<int>& v2){
  auto result = merge(v1,v2);
  //------  debug print result
  for(auto k: result){
    std::cout << k << ",";
  }
  std::cout << "\n";
  //------
  
  if(result.size()<2)
    return result[0];
  
  int remainder = result.size()%2;
  int quotient = (int)(result.size()/2);
  if(remainder==0){
    return (result[quotient-1] + result[quotient])/2.0;
  }else{
    return result[quotient];
  }
}

int main(){
  std::vector<int> v1{1,3};
  std::vector<int> v2{2};
  std::cout << "median = "<< median(v1,v2) << std::endl;
  
  std::vector<int> v3{1,2};
  std::vector<int> v4{3,4};
  std::cout << "median = "<< median(v3,v4) << std::endl;
  
  std::vector<int> v5{4,9,11};
  std::vector<int> v6{1,3,4};
  std::cout << "median = "<< median(v5,v6) << std::endl;
}