Find median of two sorted arrays, with complexity of min(log(m),log(n)) 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 &lt;iostream&gt;
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 &lt;&lt; " enter the size of the first array: ";
    cin &gt;&gt; m;
    a = new int[m];
    cout &lt;&lt; " \nenter the size of the second array:";
    cin &gt;&gt; n;
    b = new int[n];

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

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


    cout &lt;&lt; "\nthe median of the merged array is : " &lt;&lt; findMedian(a, b,  m,  n)&lt;&lt; '\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 &lt;= imax)
    {
        i = (imin + imax) / 2;
        j = half_len - i;

        if (i &lt; m &amp;&amp; b[j - 1] &gt; a[i])
            imin = i + 1;

        else if (i &gt; 0 &amp;&amp; a[i - 1] &gt; 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 &gt; b ? a : b;
}

int min(int a, int b)
{
    return a &lt; 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
Consistent whitespace


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



isn't even consistent within the same line about whether &lt;&lt; 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 &lt;= 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.