Implementation of the median of two sorted arrays of equal size in C++

Question

I tried to implement the above algorithm in C++, but somehow I am getting a rounding error when computing the length of half of the array.

Attempt:

#include <iostream>
#include <math.h>
using namespace std;

void print_array(int arr[], int size){
    for(int i = 0; i < size; i++){
        cout << arr[i] << "-";
    }
    cout << endl;
}

float median_h(int arr[], int size){
  float median = 0.0;
  if(size%2 == 0)
    median = (arr[size/2] + arr[(size/2)-1])/2;
  else median = arr[(int)ceil(size/2)];
  return median;
}

float median(int arr1[], int arr2[], int size_1, int size_2){
   cout << size_1 << endl;
   print_array(arr1,size_1);
   cout << size_2 << endl;
   print_array(arr2,size_2);
   cout << endl;
   float m1 = median_h(arr1,size_1);
   float m2 = median_h(arr2,size_2);
   float median_res = 0.0;
   if(size_1 == 1)
      median_res = (arr1[0] + arr2[0])/2;
   else if(m1 == m2)
      median_res = m1;
   else{
     int index = 0;
     int size = ceil(size_1/2);
     (size_1 % 2 == 0)? index = size_1/2 : index = floor(size_1/2); 
     if(m1 < m2)
       median_res = median(arr1 + index,arr2, size, size);    
     else
       median_res = median(arr1,arr2 + index, size, size);
   }
   return median_res;
}



int main(void){
    int arr1[] = {1,12,15,26,38};
    int arr2[] = {2,13,17,30,45};

    float med = median(arr1,arr2,5,5);
    cout << med << endl;

}

This is the output:

  output:

    5
    1-12-15-26-38-
    5
    2-13-17-30-45-

    2
    15-26-
    2
    2-13-

    1
    15-
    1
    13-

    14

I am expecting a length of 3 in the second recursive iteration, but I am getting 2. I don't know what's wrong with ceil(5/2). It's supposed to be 3.

it might be possible that ceil(5/2) computes as follows: 5 is treated as int and 2 also so first (int)5/(int)2 = 2. => ceil(2) = 2. Solution here would be to try ceil((float)5/(float)2). (Or at least cast one of them) — Robin B, Jan 18 '18 at 06:25
That's how integer division works in C++. BTW: Voting to close as off-topic, because you didn't extract a minimal example, which is required per site guidelines. — Ulrich Eckhardt, Jan 18 '18 at 06:28
This is more of a simple typographical error which is not useful for future visitors. — user202729, Jan 18 '18 at 06:30
[Duplicate: "Fast ceiling of an integer division in C / C++ "](https://stackoverflow.com/questions/2745074/fast-ceiling-of-an-integer-division-in-c-c). — user202729, Jan 18 '18 at 06:30

Jeremy Friesner · Accepted Answer · 2018-01-18T19:28:50.247

 int size = ceil(size_1/2);

Since size_1 is of type int, dividing it by 2 is implicitly equivalent to taking the floor of the division. e.g. if size_1 was equal to 3, then (size_1/2) will return 1, not 1.5.

Therefore, ceil() isn't going to get you what you want here, because the value being passed to it is already floored.

You could do it like this instead:

int size = ceil(size_1/2.0f);  // now we're dividing by a float, so the result will be non-integer

... but you could get the same result without having to resort to floating point math simply by adding 1 to the value before dividing:

int size = (size_1+1)/2;

score 1 · Answer 2 · answered Jan 18 '18 at 06:41

/* Function to get median of a sorted array */
int median_h(int arr[], int n)
{
    if (n%2 == 0)
        return (arr[n/2] + arr[n/2-1])/2;
    else
        return arr[n/2]; // <- HERE
    // also since n is int, you can do ( n << 1 )
    // it's faster
}

/* This function returns median of ar1[] and ar2[].
   Assumptions in this function:
   Both ar1[] and ar2[] are sorted arrays
   Both have n elements */
int median(int ar1[], int ar2[], int n)
{
    /* return -1  for invalid input */
    if (n <= 0)
        return -1;
    if (n == 1)
        return (ar1[0] + ar2[0])/2;
    if (n == 2)
        return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;

    int m1 = median_h(ar1, n); /* get the median of the first array */
    int m2 = median_h(ar2, n); /* get the median of the second array */

    /* If medians are equal then return either m1 or m2 */
    if (m1 == m2)
        return m1;

    /* if m1 < m2 then median must exist in ar1[m1....] and
        ar2[....m2] */
    if (m1 < m2)
    {
        if (n % 2 == 0)
            return median(ar1 + n/2 - 1, ar2, n - n/2 +1);
        return median(ar1 + n/2, ar2, n - n/2);
    }

    /* if m1 > m2 then median must exist in ar1[....m1] and
        ar2[m2...] */
    if (n % 2 == 0)
        return median(ar2 + n/2 - 1, ar1, n - n/2 + 1);
    return median(ar2 + n/2, ar1, n - n/2);
}

use this website : https://www.geeksforgeeks.org/median-of-two-sorted-arrays/

yeah. I decided to do this on my own, but I learned about that algorithm in that web-site. — patzi, Jan 18 '18 at 06:43
why is it better to stop the recursion at this point? if (n == 2) return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2; — patzi, Jan 18 '18 at 06:53

Implementation of the median of two sorted arrays of equal size in C++

2 Answers2