Median of two sorted arrays

We are given two arrays of integers and both of them are sorted. Find the algorithm to determine the median faster than O(N log N).

Let the arrays be called A1 and A2, and have size N and M respectively. If we would put the numbers into one array, then we would know that the median will be located at (N + M + 1)/2 if N + M is odd, otherwise we would take the ((N + M)/2 + (N + M + 1)/2)/2. However we won’t put them into one array. Instead we will browse them simultaneously.

int median(vector<int> a1, vector<int> a2){
 int i1, i2;
 i1 = i2 = 0;
 int merged_size = a1.size() + a2.size();
 int last, last_last;
 last = max(a1[0], a2[0]);
 last_last = min(a1[0], a2[0]);

 while(i1 + i2 < ((merged_size + 1)/2)){
  last_last = last;
  if(i1 < a1.size() && a[i1] < a[i2]){
   last = array[i1];
   i1++;
  }
  else if(i2 < a2.size()){
   last = array[i+1]
   i2++;
  }
 }
 if(merged_size % 2)
  return last; // the middle element
 else return (last + last_last)/2;
}

Thanks to using two extra variables we didn’t have to introduce stack or any other structure that would monitor the order of elements. Thanks to that the memory complexity of the problem is constant.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s