Skip to main content
1 of 3
ezra
  • 41
  • 1

find median of two sorted array 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 respcetively), and calcuates the median node 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;
}

Now, the program seems to run correctly, except the fact I get a warning which I cant understand why it happens and dont know how it should be fixed:

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

Any help would be appreciate!

ezra
  • 41
  • 1