Find median of two sorted arrays, with complexity of min(log(m),log(n))

Question

I wrote a program which gets two sorted arrays a and b (with sizes m and n respectively), and calculates the median value of these arrays without merging them.

Here is my code:

#include <iostream>
using namespace std;

int findMedian(int a[], int b[], int m, int n);
int max(int a, int b);
int min(int a, int b);


void main()
{

    int m, n, *a, *b, i;

    cout << " enter the size of the first array: ";
    cin >> m;
    a = new int[m];
    cout << " \nenter the size of the second array:";
    cin >> n;
    b = new int[n];

    cout << " \nthe numbers of the first array in sorted way: ";
    for (i = 0; i < m; i++)
        cin >> a[i];

    cout << "\nplease enter your numbers of the second array in sorted way: ";
    for (i = 0; i < n; i++)
        cin >> b[i];


    cout << "\nthe median of the merged array is : " << findMedian(a, b,  m,  n)<< '\n';

    free(b);
    free(a);
}

int findMedian(int a[], int b[], int m, int n)
{

    int imin = 0, imax = m, half_len = (m + n + 1) / 2;
    int i, j, max_of_left, min_of_right;

    while (imin <= imax)
    {
        i = (imin + imax) / 2;
        j = half_len - i;

        if (i < m && b[j - 1] > a[i])
            imin = i + 1;

        else if (i > 0 && a[i - 1] > b[j])
            imax = i - 1;

        else
        {

            if (i == 0)
                max_of_left = b[j - 1];

            else if (j == 0)
                max_of_left = a[i - 1];

            else
                 max_of_left = max(a[i - 1], b[j - 1]);

            if ((m + n) % 2 == 1)
                return max_of_left;

            if (i == m)
                min_of_right = b[j];
            else if (j == n)
                min_of_right = a[i];
            else
                min_of_right = min(a[i], b[j]);

                return min(max_of_left,min_of_right);
        }
    }

}


int max(int a, int b)
{
    return a > b ? a : b;
}

int min(int a, int b)
{
    return a < b ? a : b;
}

One particular thing I'd like to improve is that although the program seems to run correctly, I get this warning; I can't understand why it happens and don't know how it should be fixed:

warning C4715: 'findMedian': not all control paths return a value

Answer 1

Consistent whitespace

    cout << "\nthe median of the merged array is : " << findMedian(a, b,  m,  n)<< '\n';

isn't even consistent within the same line about whether << should have spaces on both sides or not. I'm surprised your editor didn't auto-format it.

There is also a wide variety of whitespace in the strings which are used to prompt for input.

Also in this category,

                return min(max_of_left,min_of_right);

appears to be indented too far. Well, either that or there are some missing {} to include it with the previous statement in a single block.

---

Memory management

void main()
{
    ...
    a = new int[m];
    ...
    b = new int[n];
    ...
    free(b);
    free(a);
}

Are you sure? This looks fishy to me. There's no call to malloc or friends, so why is there a call to free?.

---

Warning

Let's simplify the code a bit...

int findMedian(int a[], int b[], int m, int n)
{
    int imin = 0, imax = m, half_len = (m + n + 1) / 2;
    int i, j, max_of_left, min_of_right;

    while (imin <= imax)
    {
        ...
    }
}

Now can you see why "not all control paths return a value"?

Hint: what's the loop invariant?

---

Performance claims

The title of this question is "Find median of two sorted arrays, with complexity of min(log(m),log(n))". That's impossible: if I guarantee that the second array is of length at most 1, you're promising to find the median of the other array with complexity bounded above by 0.

I think you can claim \$\log(m+n)\$, but some comments to justify correctness and performance would be nice.