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

• yuri: Use a better compiler, preferably one that doesn't allow void main(). GCC has this to say about your warning "control reaches end of non-void function [-Wreturn-type]" which is even clearer.
• rolfl: Please create a registered account if you want to edit questions. This post can be merged in to a registered account if you make one.

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.

• Jerry Coffin: As far as complexity cares, O(any constant) is the same. If one of the arrays is empty, it's entirely reasonable to determine the median of the other in constant time (in other words, I think what he claims is possible, though the way he's stated it could be somewhat confusing).
• Peter Taylor: @JerryCoffin, not quite. \$O(1)\$ is the same as \$O(2)\,ドル but not the same as \$O(0)\$ or \$O(-\infty)\$.
• Jerry Coffin: Since N is the number of items being processed, O(negative) doesn't make any sense. O(0), however, does--and at at a quick glance through CLRS and Knuth V1, I can't find anything saying that N must be strictly positive, as opposed to merely non-negative. There's certainly some variation in how people use big-O notation, but the condition you're trying to claim doesn't seem to fit with typical usage.
• Peter Taylor: @JerryCoffin, I think the real issue is that \$O\$ notation is frequently abused, and in particular multivariate use is nearly always abusive because it doesn't specify the interaction between the limit-taking in the different variables. I think you will at least agree that \$O(\min(\log m, \log 0))\$ in one variable is borked.
• Jerry Coffin: Well, given that log(0) is undefined, I'd agree that pretty nearly anything that involves it is probably not very good.